传送门：poj3159 Candies
题意：30000点，150000边的稀疏图求单源最短路，读入“A B C”，就添加A->B的有向边，权值为C，然后求1到N的最短路。因为N号说了，他只跟一号比较。
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=3e4+10;
int n,m;struct CNode{int k; //有向边的终点 int w; //权值，或当前k到源点的距离 CNode(int k_,int w_):k(k_),w(w_){}CNode(){}bool operator < (const CNode &d)const{return w>d.w;}
};vector<vector<CNode> >v; //v是整个图的邻接表int Dijkstra(){priority_queue<CNode>pq;bool vis[maxn];memset(vis,0,sizeof(vis));pq.push(CNode(1,0)); //源点是1号点，它到自己的距离是0CNode p;while(!pq.empty()){p=pq.top();pq.pop();if(vis[p.k]) continue; //已经求出了最短路vis[p.k]=true;if(p.k==n) break; //因为只要求出源点是1，终点是n这条路的最短路径即可for(int i=0,j=v[p.k].size();i<j;i++){CNode q;q.k=v[p.k][i].k;if(vis[q.k]) continue;q.w=p.w+v[p.k][i].w; /*注意这条语句的理解，p.k这个顶点到源点的最短距离已求出 ，q.k这个点如果到源点的最短距离还没算，那么最短就是p.w+(p.k,q.k这两个顶点所连边的权值)*/pq.push(q); //队列已经有q.k也没关系}}return p.w;
}int main(){scanf("%d%d",&n,&m);v.clear();v.resize(n+1);int a,b,c;for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);v[a].push_back(CNode(b,c));}int res=Dijkstra();printf("%d\n",res);return 0;
}