设顶点为n，边数为m

如果边数m大约为n的平方则为稠密图，用邻接矩阵较好

否则如果为稀疏图用邻接表+堆优化较好

朴素版

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=505; int dis[N],g[N][N],n,m; bool st[N]; int disjtra() { memset(dis,0x3f,sizeof dis); dis[1]=0; for(int i=0;i<n-1;i++) { int t=-1; for(int j=1;j<=n;j++) { if(!st[j]&& (t==-1||dis[t]>dis[j]) ) t=j; } if(t==n)break; st[t]=true; for(int j=1;j<=n;j++) { dis[j]=min(dis[j],dis[t]+g[t][j]); } } if(dis[n]==0x3f3f3f3f)return -1; return dis[n]; } int main() { memset(g,0x3f,sizeof g); cin>>n>>m; for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; g[a][b]=min(g[a][b],c); } cout<<disjtra()<<endl; }

堆优化

注意数组大小

h,st素组开顶点大小，e,w,ne,开边的大小

#include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; typedef pair<int,int> PLL; const int N=1e5+10,M=505; int e[N],h[M],w[N],ne[N],n,m,idx,dis[N]; bool st[M]; priority_queue<PLL,vector<PLL>,greater<PLL> > heap; void add(int a,int b,int c) { e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void disjtra() { memset(dis,0x3f,sizeof(dis)); dis[1]=0; heap.push({0,1}); while(heap.size()) { auto t=heap.top(); heap.pop(); int ver=t.second,distance=t.first; if(st[ver])continue; st[ver]=true; for(int i=h[ver];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]>distance+w[i]) { dis[j]=distance+w[i]; heap.push({dis[j],j}); } } } if(dis[n]==0x3f3f3f3f)dis[n]=-1; } int main() { memset(h,-1,sizeof h); cin>>n>>m; for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } disjtra(); cout<<dis[n]<<endl; }