这个题就是很简单的最短路问题。这里记录下康复训练的代码。
spfa最坏时间复杂度是O(VE)，Dijkstra时间复杂度是O(E+VlogV)。
spfa:
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
const int maxn=505;
const int INF=0x3f3f3f3f;
int N,M,S,D,u,v,d,c;
struct P
{
int to,dis,cost;
};
vector<P> edge[maxn];
int distan[maxn],co[maxn],path[maxn],vis[maxn];
void dijkstra()
{
memset(distan,INF,sizeof(distan));
memset(co,INF,sizeof(co));
queue<int> qu;
qu.push(S);
distan[S]=0;
co[S]=0;
while(!qu.empty())
{
int U=qu.front();
qu.pop();
vis[U]=0;
for(int i=0;i<edge[U].size();i++)
{
int V=edge[U][i].to;
if(distan[V]>distan[U]+edge[U][i].dis)
{
distan[V]=distan[U]+edge[U][i].dis;
co[V]=co[U]+edge[U][i].cost;
path[V]=U;
if(!vis[V])
{
vis[V]=1;
qu.push(V);
}
continue ;
}
else if(distan[V]==distan[U]+edge[U][i].dis)
{
if(co[V]>co[U]+edge[U][i].cost)
{
co[V]=co[U]+edge[U][i].cost;
path[V]=U;
if(!vis[V])
{
vis[V]=1;
qu.push(V);
}
}
}
}
}
}
void DFS(int x)
{
if(path[x]==S)
{
cout << S << " " << x;
return ;
}
else DFS(path[x]);
cout << " " << x;
}
int main()
{
scanf("%d%d%d%d",&N,&M,&S,&D);
for(int i=1;i<=M;i++)
{
scanf("%d%d%d%d",&u,&v,&d,&c);
edge[u].push_back(P{v,d,c});
edge[v].push_back(P{u,d,c});
}
dijkstra();
DFS(D);
cout << " " << distan[D] << " " << co[D] << endl;
return 0;
}
Dijkstra:
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
const int maxn=505;
const int INF=0x3f3f3f3f;
int N,M,S,D,u,v,d,c;
struct P
{
int to,dis,cost;
bool operator<(const P &a)const
{
return dis>a.dis;
}
};
vector<P> edge[maxn];
int distan[maxn],co[maxn],path[maxn],vis[maxn];
void dijkstra()
{
memset(distan,INF,sizeof(distan));
memset(co,INF,sizeof(co));
memset(vis,0,sizeof(vis));
priority_queue<P> qu;
qu.push(P{S,0});
distan[S]=0;
co[S]=0;
while(!qu.empty())
{
P U=qu.top();
qu.pop();
if(vis[U.to]) continue;
vis[U.to]=1;
for(int i=0;i<edge[U.to].size();i++)
{
P V=edge[U.to][i];
if(distan[V.to]>distan[U.to]+edge[U.to][i].dis)
{
distan[V.to]=distan[U.to]+edge[U.to][i].dis;
co[V.to]=co[U.to]+edge[U.to][i].cost;
path[V.to]=U.to;
qu.push(P{V.to,distan[V.to]});
continue ;
}
else if(distan[V.to]==distan[U.to]+edge[U.to][i].dis)
{
if(co[V.to]>co[U.to]+edge[U.to][i].cost)
{
co[V.to]=co[U.to]+edge[U.to][i].cost;
path[V.to]=U.to;
qu.push(P{V.to,distan[V.to]});
}
}
}
}
}
void DFS(int x)
{
if(path[x]==S)
{
cout << S << " " << x;
return ;
}
else DFS(path[x]);
cout << " " << x;
}
int main()
{
scanf("%d%d%d%d",&N,&M,&S,&D);
for(int i=1;i<=M;i++)
{
scanf("%d%d%d%d",&u,&v,&d,&c);
edge[u].push_back(P{v,d,c});
edge[v].push_back(P{u,d,c});
}
dijkstra();
DFS(D);
cout << " " << distan[D] << " " << co[D] << endl;
return 0;
}
然而第一次的AC代码是不加vis数组优化的spfa，这样会使得时间增加（好久没写了就乱写一通QAQ）
PAT-Travel Plan (30)-Dijkstra和SPFA
原文：https://www.cnblogs.com/JustDoA/p/10404641.html