题目地址：http://poj.org/problem?id=3159
时间挺紧的
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=30000+5;
typedef pair<int,int> pii;
struct Edge{int to,weight;Edge(int to,int weight):to(to),weight(weight){}
};
vector<vector<Edge> > G(maxn); //更快，关键
struct Dijkstra{ //打包在Dijkstra中 int n,m;bool done[maxn];int dist[maxn];int p[maxn];Dijkstra(int n):n(n){for(int i=0;i<n;i++) G[i].clear();}void AddEdge(int from,int to,int weight){G[from].push_back(Edge(to,weight)); //保存from出发的边 }void dijkstra(int s){priority_queue<pii,vector<pii>,greater<pii> > Q;memset(dist,0x7f,sizeof(dist)); //初始化为无穷大 memset(done,false,sizeof(false));dist[s]=0;Q.push(pii(0,s)); //pii (dist ,u)while(!Q.empty()){int u=Q.top().second; Q.pop();if(done[u]) continue; //可改为if(dist[u]!=Q.top().first) continue; done[u]=true; for(int i=0;i<G[u].size();i++){Edge& e=G[u][i];int v=e.to ,w=e.weight;if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;p[v]=u; //记录到各点的最短路径 Q.push(pii(dist[v],v));}}}}
};
int main()
{int n,m,u,v,w;cin>>n>>m; //n 点 , m 边 Dijkstra d(n);for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);d.AddEdge(u,v,w);}d.dijkstra(1); //1点出发 cout<<d.dist[n]<<endl; //到n的最短路径 return 0;
}