题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805358663417856
题目大意，给出一个有向图，edge的属性有路程和花费时间。求两条路径：
- 路程最短的，如果有多条，取最快的
- 最快的，如果有多条，取经过节点数最少的
思路：经典Dijkstra，但是忘记了多个条件的Dijkstra怎么写。。于是参考了柳神的代码。原来只需要同时维护两个标准，第一个相等时再看第二个即可。
for (int w = 0; w < N; w++) {
if (!known[w] && mat_len[v][w] != MAX) {
if (cost_len[v] + mat_len[v][w] < cost_len[w]) {
cost_len[w] = cost_len[v] + mat_len[v][w];cost_time[w] = cost_time[v] + mat_time[v][w];pre_len[w] = v;}else if (cost_len[v] + mat_len[v][w] == cost_len[w]) {
if (cost_time[w] > cost_time[v] + mat_time[v][w]) {
cost_time[w] = cost_time[v] + mat_time[v][w];pre_len[w] = v;}}}}
注意初始化，第一次Dijkstra和第二次Dijkstra之前都要做相应的初始化。
void init2() {
for (int i = 0; i < N; i++) {
cost_time[i] = MAX;known[i] = false;}
}
如果只要一种路径的话其实不用开vector来存，只需要根据pre[]数组从终点向起点找就行了。不过本题有两个路径，所以要都先存下来，最后判断是否相等。
void getTimePath(int v) {
time_path.push_back(v);if (v == src) return;getTimePath(pre_time[v]);
}
完整代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>using namespace std;int mat_len[501][501];
int mat_time[501][501];
int cost_len[501];
int cost_time[501];
int cost_node[501];
int pre_len[501];
int pre_time[501];
bool known[501];
int N, M, src, des;
const int MAX = 10000007;
vector<int> len_path, time_path;void init() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)mat_time[i][j] = mat_len[i][j] = MAX;cost_time[i] = cost_len[i] = MAX;pre_time[i] = pre_len[i] = i;known[i] = false;}
}void input() {
int v1, v2, one_way, len, time;for (int i = 0; i < M; i++) {
scanf("%d %d %d %d %d", &v1, &v2, &one_way, &len, &time);mat_len[v1][v2] = len;mat_time[v1][v2] = time;if (one_way == 0) {
mat_len[v2][v1] = mat_len[v1][v2];mat_time[v2][v1] = mat_time[v1][v2];}}
}void Dijkstra_len() {
while (1) {
int v = -1;int min_dis = MAX;for (int i = 0; i < N; i++) {
if (!known[i] && cost_len[i] < min_dis) {
min_dis = cost_len[i];v = i;}}if (v == -1) break;known[v] = true;for (int w = 0; w < N; w++) {
if (!known[w] && mat_len[v][w] != MAX) {
if (cost_len[v] + mat_len[v][w] < cost_len[w]) {
cost_len[w] = cost_len[v] + mat_len[v][w];cost_time[w] = cost_time[v] + mat_time[v][w];pre_len[w] = v;}else if (cost_len[v] + mat_len[v][w] == cost_len[w]) {
if (cost_time[w] > cost_time[v] + mat_time[v][w]) {
cost_time[w] = cost_time[v] + mat_time[v][w];pre_len[w] = v;}}}}}
}void init2() {
for (int i = 0; i < N; i++) {
cost_time[i] = MAX;known[i] = false;}
}void Dijkstra_time() {
while (1) {
int v = -1;int min_time = MAX;for (int i = 0; i < N; i++) {
if (!known[i] && cost_time[i] < min_time) {
min_time = cost_time[i];v = i;}}if (v == -1) break;known[v] = true;for (int w = 0; w < N; w++) {
if (!known[w] && mat_time[v][w] != MAX) {
if (cost_time[v] + mat_time[v][w] < cost_time[w]) {
cost_time[w] = cost_time[v] + mat_time[v][w];cost_node[w] = cost_node[v] + 1;pre_time[w] = v;}else if (cost_time[v] + mat_time[v][w] == cost_time[w]) {
if (cost_node[w] > cost_node[v] + 1) {
cost_node[w] = cost_node[v] + 1;pre_time[w] = v;}}}}}
}void getLenPath(int v) {
len_path.push_back(v);if (v == src) return;getLenPath(pre_len[v]);
}void getTimePath(int v) {
time_path.push_back(v);if (v == src) return;getTimePath(pre_time[v]);
}int main() {
scanf("%d %d", &N, &M);init();input();scanf("%d %d", &src, &des);cost_len[src] = 0;Dijkstra_len();getLenPath(des);init2();cost_time[src] = 0;Dijkstra_time();getTimePath(des);if (time_path == len_path) {
printf("Distance = %d; Time = %d: %d", cost_len[des], cost_time[des], src);for (int i = len_path.size()-2; i >= 0; i--)printf(" -> %d", len_path[i]);}else {
printf("Distance = %d: %d", cost_len[des], src);for (int i = len_path.size()-2; i >= 0; i--)printf(" -> %d", len_path[i]);printf("\nTime = %d: %d", cost_time[des], src);for (int i = time_path.size()-2; i >= 0; i--)printf(" -> %d", time_path[i]);}return 0;
}