迪杰斯特拉+逆序记录路径
默认只有一条最优路径
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 500+5;
int dis[N], Cost[N];
bool vis[N];
struct Node {
int v, w, c;
Node() {
v = -1;
w = inf;
c = inf;
}
Node(int a, int b, int tc) {
v = a;
w = b;
c = tc;
}
};
vector<Node> V[N];
vector<int> pre[N];//记录路径
void init() {
for(int i=0; i<N; i++) {
vis[i] = false;
dis[i] = inf;
Cost[i] = inf;
}
}
void dfs(int s, int t) {
//for(int i=0; i<pre[t].size(); i++)
{
if(s == pre[t][0]) {
cout << s << " ";
return;
} else
dfs(s, pre[t][0]);
}
cout << pre[t][0] << " ";
}
void Dij(int s, int t) {
init();
queue<Node> q;
Node tmp(s, 0, 0);
q.push(tmp);
vis[s] = true;
dis[s] = 0;
Cost[s] = 0;
while(!q.empty()) {
tmp = q.front();
q.pop();
for(int i=0; i<V[tmp.v].size(); i++) {
Node tmp2 = V[tmp.v][i];
if(dis[tmp2.v] > dis[tmp.v]+tmp2.w) {
Cost[tmp2.v] = Cost[tmp.v]+tmp2.c;
// cout << tmp.v << tmp2.v << "=="<< Cost[tmp.v] << "+" << tmp2.c << "=" << Cost[tmp2.v]<< endl;
dis[tmp2.v] = dis[tmp.v]+tmp2.w;
pre[tmp2.v].clear();
pre[tmp2.v].push_back(tmp.v);
} else if(dis[tmp2.v] == dis[tmp.v]+tmp2.w) {
if(Cost[tmp2.v] > Cost[tmp.v]+tmp2.c) {
pre[tmp2.v].clear();
pre[tmp2.v].push_back(tmp.v);
Cost[tmp2.v] = Cost[tmp.v]+tmp2.c;
}
}
if(!vis[tmp2.v]) {
vis[tmp2.v] = true;
q.push(tmp2);
}
}
}
dfs(s, t);
cout << t << " "<< dis[t] << " " << Cost[t] << endl;
}
int main() {
int n, m, s, d;
cin >> n >> m >> s >> d;
for(int i=0; i<m; i++) {
int u, v, d, c;
Node tmp1;
cin >> u >> v >> d >> c;
tmp1.v= v, tmp1.w = d, tmp1.c = c;
V[u].push_back(tmp1);
tmp1.v = u;
V[v].push_back(tmp1);
}
Dij(s, d);
return 0;
}