题意:给定起点和终点,给定无向图和每一条边的长度和花费,求出从起点到终点的最短距离,如果路径不唯一输出花费最少的那一条路径,并输出最短距离和花费。
思路:dijkstra模板题,在发现两个路径长度相同时,如果一条路的花费更少则需要更新花费和路径,图用邻接矩阵存,邻接表复杂度会高一些
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define PII pair<int, int>
#define x first
#define y second
const int N = 510;
PII g[N][N];
int n, m, s, d;
int dist[N], cost[N];
bool st[N];
vector<int> path[N];
void dijkstra(int s){
memset(dist, 0x3f, sizeof dist);
memset(cost, 0x3f, sizeof cost);
cost[s] = dist[s] = 0;
path[s].push_back(s);
for(int i = 0; i < n; i ++){
int t = -1;
for(int j = 0; j < n; j ++)
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = 1;
for(int j = 0; j < n; j ++){
if(dist[j] > dist[t] + g[t][j].x){
dist[j] = dist[t] + g[t][j].x;
cost[j] = cost[t] + g[t][j].y;
path[j] = path[t];
path[j].push_back(j);
}
if(dist[j] == dist[t] + g[t][j].x){
if(cost[j] > cost[t] + g[t][j].y){
cost[j] = cost[t] + g[t][j].y;
path[j] = path[t];
path[j].push_back(j);
}
}
}
}
}
int main(){
memset(g, 0x3f, sizeof g);
cin >> n >> m >> s >> d;
while(m --){
int a, b, w, c;
cin >> a >> b >> w >> c;
g[a][b] = g[b][a] = {w, c};
}
dijkstra(s);
for(int i = 0; i < path[d].size(); i ++) cout << path[d][i] << ‘ ‘;
cout << dist[d] << ‘ ‘ << cost[d];
return 0;
}