本题目的难点在于存储最短路径上的城市,如何处理最短路径和最小费用之间的关系
代码:
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int N=600;
int h[N],e[2*N],ne[2*N],s[2*N],w[2*N];
int dist[N],ex[N];
int idx;
int n,m,l,r;
int pre[N];
void add(int a,int b,int c,int d){
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
s[idx]=d;
h[a]=idx++;
}
typedef pair<int,int>pii;
bool st[N];
void dij(){
memset(dist,0x3f,sizeof dist);
memset(ex,0x3f,sizeof ex);
priority_queue<pii,vector<pii>,greater<pii> >heap;
dist[l]=0;
ex[l]=0;
heap.push({0,l});
while(!heap.empty()){
auto t=heap.top();
heap.pop();
int a=t.first;
int b=t.second;
if(st[b])
continue;
st[b]=true;
for(int i=h[b];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>a+w[i]){
dist[j]=a+w[i];
heap.push({dist[j],j});
ex[j]=ex[b]+s[i];//本步骤随着dist更新,ex也必须更新,如果没有这句,那么ex[i]一直是0x3f
//并且本步骤不能写成ex[j]=min(ex[j],ex[b]+s[i]);花费的钱的路径和最短路径必须一致!!!
pre[j]=b;//存储本节点的上一个节点!!!
}
else if(dist[j]==a+w[i]){
if(ex[j]>ex[b]+s[i]){
ex[j]=ex[b]+s[i];
pre[j]=b;//!!!
}
}
}
}
}
int main(){
cin>>n>>m>>l>>r;
memset(h,-1,sizeof h);
while(m--){
int a,b,c,d;
cin>>a>>b>>c>>d;
add(a,b,c,d);
add(b,a,c,d);
}
dij();
vector<int>res;
res.push_back(r);
for(int i=r;i!=l;i=pre[i]){
res.push_back(pre[i]);
}
for(int i=res.size()-1;i>=0;i--){
cout<<res[i]<<' ';
}
cout<<dist[r]<<' '<<ex[r];
return 0;
}