题意：求1~n的最短路径，不能用vector存边，要用邻接表
#include <iostream> #include <algorithm> #include <string.h> #include <stdio.h> #include <vector> #include <queue> using namespace std; #define LL long long #define maxn 100005 struct node { int to,nex; LL v; }p[2*maxn]; int h[maxn],cnt,pre[maxn],n,m; LL d[maxn]; bool inq[maxn]; void init() { for(int i=0;i<maxn;i++)inq[i]=0; for(int i=0;i<maxn;i++)d[i]=999999999999999; for(int i=0;i<maxn;i++)pre[i]=0; memset(h,0,sizeof(h)); cnt=0; } void add(int u,int v,LL w) { cnt++; p[cnt].v=w; p[cnt].to=v; p[cnt].nex=h[u]; h[u]=cnt; } void print(int t) { if(t!=1) print(pre[t]); printf("%d ",t); } int main() { while(cin>>n>>m) { init(); for(int i=0;i<m;i++) { int x,y; LL z; scanf("%d%d%lld",&x,&y,&z); add(x,y,z); add(y,x,z); } queue<int>Q; Q.push(1); d[1]=0; inq[1]=1; while(!Q.empty()) { int now=Q.front(); Q.pop();inq[now]=0; for(int i=h[now];i>0;i=p[i].nex) { if(d[p[i].to]>d[now]+p[i].v) { d[p[i].to]=d[now]+p[i].v; pre[p[i].to]=now; if(inq[p[i].to]==1) continue; inq[p[i].to]=1; Q.push(p[i].to); } } } if(d[n]==999999999999999) printf("-1 "); else print(n); } return 0; }