1、dijkstra
同时处理多个标准。
#include <cstdio>
#include <climits>
#include <algorithm>
#include <stack>
using namespace std;
struct edge{
int dis, price;
edge(){
dis = 0;
}
};
const int maxc = 500;
const int INF = INT_MAX;
int N, M, S, D;
edge graph[maxc][maxc];
bool confirmed[maxc]={};
int di[maxc]; //S到城市i的最短距离
int cost[maxc]; //S到城市i在距离最短条件下，最低cost
int pre[maxc]; //记录路径
void init();
void dijkstra();
int main(){
scanf("%d%d%d%d", &N, &M, &S, &D);
while(M--){
int c1, c2, d, c;
scanf("%d%d%d%d", &c1, &c2, &d, &c);
graph[c1][c2].dis = graph[c2][c1].dis = d;
graph[c1][c2].price = graph[c2][c1].price = c;
}
init();
dijkstra();
stack<int> path;
int v = D;
while(v!=S){
path.push(v);
v = pre[v];
}
path.push(S);
while(!path.empty()){
printf("%d ", path.top());
path.pop();
}
printf("%d %d", di[D], cost[D]);
return 0;
}
void init(){
fill(di, di+N, INF);
di[S] = 0;
cost[S] = 0;
for(int i=0; i<N; i++) pre[i] = i;
return;
}
void dijkstra(){
for(int k=0; k<N; k++){
int city=-1, min_d=INF;
for(int i=0; i<N; i++){
if(!confirmed[i] && di[i]<min_d){
city = i;
min_d = di[i];
}
}
if(city==-1) return;
confirmed[city] = true;
for(int i=0; i<N; i++){
if(!confirmed[i] && graph[city][i].dis!=0){
if(di[city]+graph[city][i].dis<di[i]){
//在第一标准上更优
di[i] = di[city]+graph[city][i].dis;
cost[i] = cost[city] + graph[city][i].price;
pre[i] = city;
}
else if(di[city]+graph[city][i].dis==di[i] && cost[city]+graph[city][i].price<cost[i]){
//第一标准相同，第二标准更优
cost[i] = cost[city] + graph[city][i].price;
pre[i] = city;
}
}
}
}
return;
}
2、dijkstra+DFS
首先只考虑第一标准，记录多条最短路径。
再深度优先遍历，找出在其他标准上更优的路径。