最短路问题有3种常用方法:
Floyd,Dijkstra,SPFA
以下为总结代码（参考）
Floyd
可求图中任意两点间的最短路
时间复杂度上有很大不足----O(N^3)
代码难度简单
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,m,k;
ll s[1005][1005];
int main()
{
memset(s,0x3f,sizeof(s));
scanf("%lld%lld%lld",&n,&m,&k);
for(ll i=1;i<=m;i++)
{
ll x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
s[x][y]=min(s[x][y],z);
}
for(ll i=1;i<=n;i++)
{
s[i][i]=0;
for(ll j=1;j<=n;j++)
{
s[j][j]=0;
for(ll o=1;o<=n;o++)
{
s[o][o]=0;
s[j][o]=min(s[j][o],s[j][i]+s[i][o]);
}
}
}
for(ll i=1;i<=k;i++)
{
ll b,e;
scanf("%lld%lld",&b,&e);
if(s[b][e]<=0x3f3f3f3f/2)
printf("%lld\n",s[b][e]);
else printf("impossible\n");
}
return 0;
}
Floyd Code
Dijkstra
可求单源最短路
一般时间复杂度----O(n^2)
优化后时间复杂度----O(m logn)
代码难度一般
1 #include<bits/stdc++.h>
2 typedef long long ll;
3 using namespace std;
4 ll n,m,now;
5 ll s[1005][1005],dis[1005];
6 bool vi[1005];
7 int main()
8 {
9 scanf("%lld%lld",&n,&m);
10 memset(s,0x3f,sizeof(s));
11 for(ll i=1;i<=n;i++) s[i][i]=0;
12 for(ll i=1;i<=m;i++)
13 {
14 ll x,y,z;
15 scanf("%lld%lld%lld",&x,&y,&z);
16 s[x][y]=min(s[x][y],z);
17 }
18 memset(dis,0x3f,sizeof(dis));
19 dis[1]=0;
20 for(ll i=1;i<n;i++)
21 {
22 ll t=0;
23 for(ll j=1;j<=n;j++)
24 {
25 if((dis[j]<dis[t]||t==0)&&!vi[j])
26 {
27 t=j;
28 }
29 }
30 vi[t]=1;
31 for(ll j=1;j<=n;j++)
32 {
33 dis[j]=min(dis[j],dis[t]+s[t][j]);
34 }
35 }
36 if(dis[n]<0x3f3f3f3f/2)
37 printf("%lld",dis[n]);
38 else printf("-1");
39 return 0;
40 }
一般 Dj Code
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef pair<long long,long long> pp;
4 typedef long long ll;
5 ll n,m;
6 ll fir[100005],to[100005],nxt[100005],w[100005],num;
7 ll dis[100005];
8 bool vis[100005];
9 void add(ll x,ll y,ll z)
10 {
11 nxt[++num]=fir[x];
12 fir[x]=num;
13 to[num]=y;
14 w[num]=z;
15 }
16 void dj()
17 {
18 memset(dis,0x3f,sizeof(dis));
19 memset(vis,0,sizeof(vis));
20 priority_queue<pp,vector<pp>,greater<pp> > q;
21 q.push(make_pair(0,1));
22 dis[1]=0;
23 while(q.size())
24 {
25 ll u=q.top().second,diss=q.top().first;
26 q.pop();
27 if(vis[u]) continue;
28 vis[u]=1;
29 for(ll i=fir[u];i;i=nxt[i])
30 {
31 ll v=to[i];
32 if(dis[v]>dis[u]+w[i])
33 {
34 dis[v]=dis[u]+w[i];
35
36 q.push(make_pair(dis[v],v));
37 }
38 }
39 }
40 }
41 int main()
42 {
43 scanf("%lld%lld",&n,&m);
44 for(ll i=1;i<=m;i++)
45 {
46 ll x,y,z;
47 scanf("%lld%lld%lld",&x,&y,&z);
48 add(x,y,z);
49 }
50 dj();
51 if(dis[n]<0x3f3f3f3f/2) printf("%lld",dis[n]);
52 else printf("-1");
53 return 0;
54 }
优化 Dj Code
SPFA
可求单源最短路
时间复杂度----O(k m)
代码难度一般
1 #include<bits/stdc++.h>
2 typedef long long ll;
3 using namespace std;
4 struct edge
5 {
6 ll nxt,to,w;
7 }e[100005];
8 ll n,m;
9 ll num,fir[100005],dis[100005],vis[100005];
10 void add(ll x,ll y,ll z)
11 {
12 e[++num].nxt=fir[x];
13 fir[x]=num;
14 e[num].to=y;
15 e[num].w=z;
16 }
17 void spfa()
18 {
19 memset(dis,0x3f,sizeof(dis));
20 dis[1]=0;
21 queue<ll> q;
22 q.push(1);
23 while(q.size())
24 {
25 ll u=q.front();q.pop();
26 vis[u]=0;
27 for(ll i=fir[u],v;v=e[i].to,i;i=e[i].nxt)
28 {
29 if(dis[v]>dis[u]+e[i].w)
30 {
31 dis[v]=dis[u]+e[i].w;
32 if(!vis[v])
33 {
34 vis[v]=1;
35 q.push(v);
36 }
37 }
38 }
39 }
40 }
41 int main()
42 {
43 scanf("%lld%lld",&n,&m);
44 for(ll i=1;i<=m;i++)
45 {
46 ll x,y,z;
47 scanf("%lld%lld%lld",&x,&y,&z);
48 add(x,y,z);
49 }
50 spfa();
51 if(dis[n]<0x3f3f3f3f/2)
52 printf("%lld",dis[n]);
53 else printf("impossible");
54 return 0;
55 }
SPFA Code
有不足之处可随时评论