Dijkstra+优先队列
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #include<queue> using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=100010; const int maxm=1000010; struct Dijkstra { int n,m,first[maxn],next[maxm],done[maxn],d[maxn]; struct Edge {int from,to,dist;}edges[maxm]; struct HeapNode { int d,u; bool operator < (const HeapNode& ths) const {return d>ths.d;} }; void init(int n) { this->n=n;m=0; memset(first,0,sizeof(first)); } void AddEdge(int u,int v,int w) { edges[++m]=(Edge){u,v,w};next[m]=first[u];first[u]=m; } void solve(int s) { priority_queue<HeapNode> Q; memset(done,0,sizeof(done)); for(int i=1;i<=n;i++) d[i]=1000000000; d[s]=0;Q.push((HeapNode){0,s}); while(!Q.empty()) { int x=Q.top().u;Q.pop(); if(done[x]) continue;done[x]=1; for(int i=first[x];i;i=next[i]) { Edge& e=edges[i]; if(d[e.to]>d[x]+e.dist) { d[e.to]=d[x]+e.dist; Q.push((HeapNode){d[e.to],e.to}); } } } } }sol; int main() { int n=read(),m=read();sol.init(n); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); sol.AddEdge(u,v,w); } sol.solve(1); for(int i=1;i<=n;i++) printf("%d ",sol.d[i]); return 0; } /* 7 8 1 3 5 1 4 2 1 5 1 4 3 2 3 6 2 4 6 3 6 7 3 5 7 1 */
SPFA
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #include<queue> using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=100010; const int maxm=1000010; struct SPFA { int n,m,first[maxn],next[maxm],inq[maxn],d[maxn]; struct Edge {int from,to,dist;}edges[maxm]; void init(int n) { this->n=n;m=0; memset(first,0,sizeof(first)); memset(inq,0,sizeof(inq)); } void AddEdge(int u,int v,int w) { edges[++m]=(Edge){u,v,w};next[m]=first[u];first[u]=m; } void solve(int S) { queue<int> Q;Q.push(S); for(int i=1;i<=n;i++) d[i]=1000000000;d[S]=0; while(!Q.empty()) { int u=Q.front();Q.pop();inq[u]=0; for(int i=first[u];i;i=next[i]) { Edge& e=edges[i]; if(d[e.to]>d[u]+e.dist) { d[e.to]=min(d[e.to],d[u]+e.dist); if(!inq[e.to]) inq[e.to]=1,Q.push(e.to); } } } } }sol; int main() { int n=read(),m=read();sol.init(n); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); sol.AddEdge(u,v,w); } sol.solve(1); for(int i=1;i<=n;i++) printf("%d ",sol.d[i]); return 0; } /* 7 8 1 3 5 1 4 2 1 5 1 4 3 2 3 6 2 4 6 3 6 7 3 5 7 1 */
SPFA优化（还是有些用的）
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #include<queue> using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=100010; const int maxm=1000010; struct SPFA { int n,m,first[maxn],next[maxm],inq[maxn],d[maxn]; struct Edge {int from,to,dist;}edges[maxm]; void init(int n) { this->n=n;m=0; memset(first,0,sizeof(first)); memset(inq,0,sizeof(inq)); } void AddEdge(int u,int v,int w) { edges[++m]=(Edge){u,v,w};next[m]=first[u];first[u]=m; } void solve(int S) { deque<int> Q;Q.push_back(S); for(int i=1;i<=n;i++) d[i]=1000000000;d[S]=0; while(!Q.empty()) { int u=Q.front();Q.pop_front();inq[u]=0; for(int i=first[u];i;i=next[i]) { Edge& e=edges[i]; if(d[e.to]>d[u]+e.dist) { d[e.to]=min(d[e.to],d[u]+e.dist); if(!inq[e.to]) { inq[e.to]=1; if(!Q.empty()&&d[e.to]<d[Q.front()]) Q.push_front(e.to); else Q.push_back(e.to); } } } } } }sol; int main() { int n=read(),m=read();sol.init(n); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); sol.AddEdge(u,v,w); } sol.solve(1); for(int i=1;i<=n;i++) printf("%d ",sol.d[i]); return 0; } /* 7 8 1 3 5 1 4 2 1 5 1 4 3 2 3 6 2 4 6 3 6 7 3 5 7 1 */