#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXV=510;
const int INF=1000000000;
int n, m, from, to;
int G[MAXV][MAXV], Time[MAXV][MAXV];
int d[MAXV], t[MAXV];
bool vis[MAXV]={false};
vector<int> pre[MAXV];
void Dijkstra(int f){
fill(d,d+MAXV,INF);
d[f]=0;
for(int i=0;i<n;i++){//n次循环
int u=-1, MIN=INF;
for(int j=0;j<n;j++){
if(vis[j]==false&&d[j]<MIN){
MIN=d[j]; u=j;
}
}
if(u==-1)return;
vis[u]=true;
for(int j=0;j<n;j++){
if(vis[j]==false&&G[u][j]!=INF){
if(d[j]>d[u]+G[u][j]){
d[j]=d[u]+G[u][j];
pre[j].clear();
pre[j].push_back(u);
}
else if(d[j]==d[u]+G[u][j]){
pre[j].push_back(u);
}
}
}
}
}
vector<int> tempath, path;
int best=INF;
void DFS(int v){
if(v==from){
tempath.push_back(v);
int cost=0;
for(int i=tempath.size()-1;i>0;i--){
int id=tempath[i], idnext=tempath[i-1];
cost+=Time[id][idnext];
}
if(cost<best){
best=cost;
path=tempath;
}
tempath.pop_back();
return ;
}
tempath.push_back(v);
for(int ii=0;ii<pre[v].size();ii++){
DFS(pre[v][ii]);
}
tempath.pop_back();
}
vector<int> prepre[MAXV];
void DijkstraT(int f){
fill(vis,vis+MAXV,false);
fill(t,t+MAXV,INF);
t[f]=0;
for(int i=0;i<n;i++){//n次循环
int u=-1, MIN=INF;
for(int j=0;j<n;j++){
if(vis[j]==false&&t[j]<MIN){
MIN=t[j]; u=j;
}
}
if(u==-1)return;
vis[u]=true;
for(int j=0;j<n;j++){
if(vis[j]==false&&Time[u][j]!=INF){
if(t[j]>t[u]+Time[u][j]){
t[j]=t[u]+Time[u][j];
prepre[j].clear();
prepre[j].push_back(u);
}
else if(t[j]==t[u]+Time[u][j]){
prepre[j].push_back(u);
}
}
}
}
}
vector<int> tempathT, pathT;
int bestT=INF;
void DFST(int v){
if(v==from){
tempathT.push_back(v);
if(tempathT.size()<bestT){
bestT=tempathT.size();
pathT=tempathT;
}
tempathT.pop_back();
return ;
}
tempathT.push_back(v);
for(int ii=0;ii<prepre[v].size();ii++){
DFST(prepre[v][ii]);
}
tempathT.pop_back();
}
int main(){
int i, a, b, c, dd, e;
fill(G[0],G[0]+MAXV*MAXV,INF);
fill(Time[0],Time[0]+MAXV*MAXV,INF);
scanf("%d%d",&n,&m);
for(i=0;i<m;i++){
scanf("%d%d%d%d%d",&a,&b,&c,&dd,&e);
G[a][b]=dd; Time[a][b]=e;
if(c==0){G[b][a]=dd; Time[b][a]=e;}
}
scanf("%d%d",&from,&to);
Dijkstra(from);
DFS(to);
DijkstraT(from);
DFST(to);
if(path!=pathT){
printf("Distance = %d: ",d[to]);
for(i=path.size()-1;i>=0;i--){
printf("%d",path[i]);
if(i>0)printf(" -> ");
else printf("\n");
}
printf("Time = %d: ",t[to]);
for(i=pathT.size()-1;i>=0;i--){
printf("%d",pathT[i]);
if(i>0)printf(" -> ");
else printf("\n");
}
}
else{
printf("Distance = %d; Time = %d: ",d[to], t[to]);
for(i=path.size()-1;i>=0;i--){
printf("%d",path[i]);
if(i>0)printf(" -> ");
else printf("\n");
}
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-5995.html
