POJ 2387 Til the Cows Come Home

ダイクストラ

二分ぐらいで瞬殺。

#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;



const int INF = 100000000;
const int MAX_V = 1002;
struct edge{ int to,cost;};
typedef pair<int,int> P;
int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s){
	priority_queue<P,vector<P>,greater<P> > que;
	fill(d,d+V+1,INF);
	d[s] = 0;
	que.push(P(0,s));
	while(!que.empty()){
		P p = que.top(); que.pop();
		int v = p.second;
		if(d[v] < p.first)continue;
		for(int i = 0;i < G[v].size();i++){
			edge e = G[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}

int main(){
	int k;
	cin >> k >> V;
	while(k--){
			int a,b,c;
			cin >> a >> b >> c;
			edge tmp = {b,c};
			G[a].push_back(tmp);
			edge tmp2 = {a,c};
			G[b].push_back(tmp2);
	}
	dijkstra(1);
	cout << d[V] << endl;
	return 0;
	}