题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805358663417856
题意：
给定一个图，每天边上有时间和路程信息。要求找到路程最短且时间最短的路径，和时间最短经过的节点最少的路径。
思路：
和昨天写的那个Public Bike Arrangement差不多思路。但是因为要求两个东西所以麻烦一点。感觉好像PAT也在逐渐变难。
都是先求出最短路路径，然后在这些路径中再找到符合条件的一条。
该开始直接写dfs，最后一组数据T了。
先dijkstra再dfs的话是在最短路径上找，会减很多枝。
//#include<bits/stdc++>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdlib.h>
#include<queue>
#include<map>
#include<stack>
#include<set> #define LL long long
#define ull unsigned long long
#define inf 0x7f7f7f7f using namespace std; const int maxn = ;
int n, m;
int st, ed;
struct node{
int v;
int l, t;
node(){}
node(int _v, int _l, int _t){
v = _v;
l = _l;
t = _t;
}
};
vector<node>g[maxn]; bool vis_l[maxn], vis_t[maxn];
int d_len[maxn], d_time[maxn];
void dijkstra()
{
memset(d_len, 0x3f, sizeof(d_len));
memset(d_time, 0x3f, sizeof(d_time));
for(int i = ; i < g[st].size(); i++){
int to = g[st][i].v;
d_len[to] = g[st][i].l;
d_time[to] = g[st][i].t;
}
vis_l[st] = true;
vis_t[st] = true;
d_len[st] = ;
d_time[st] = ; for(int i = ; i < n; i++){
int id_l, id_t;
int minl = inf, mint = inf;
for(int i = ; i < n; i++){
if(!vis_l[i] && minl > d_len[i]){
minl = d_len[i];
id_l = i;
}
if(!vis_t[i] && mint > d_time[i]){
mint = d_time[i];
id_t = i;
}
} vis_l[id_l] = true;
vis_t[id_t] = true;
for(int i = ; i < g[id_l].size(); i++){
int to = g[id_l][i].v;
if(d_len[to] > d_len[id_l] + g[id_l][i].l){
d_len[to] = d_len[id_l] + g[id_l][i].l;
}
}
for(int i = ; i < g[id_t].size(); i++){
int to = g[id_t][i].v;
if(d_time[to] > d_time[id_t] + g[id_t][i].t){
d_time[to] = d_time[id_t] + g[id_t][i].t;
}
}
}
} int ans_len = inf, time_for_minlen = inf;
int length, ttime;
vector<int>minlen, path;
bool vis[maxn];
void dfs_len(int pos)
{
if(pos == ed){
if(ttime < time_for_minlen){
time_for_minlen = ttime;
minlen = path;
return;
}
}
for(int i = ; i < g[pos].size(); i++){
int to = g[pos][i].v;
if(!vis[to] && d_len[to] == d_len[pos] + g[pos][i].l){
int tmptime = ttime;
vis[to] = true;
path.push_back(to);
ttime += g[pos][i].t;
dfs_len(to);
path.pop_back();
ttime = tmptime;
vis[to] = false;
}
} } //void dfs_len(int pos)
//{
// if(length > ans_len)return;
// if(pos == ed){
// if(length < ans_len || length == ans_len && ttime < time_for_minlen){
// ans_len = length;
// time_for_minlen = ttime;
// minlen = path;
//// if(length == ans_len)len_ununique = true;
//// else len_ununique = false;
// return;
// }
// }
// for(int i = 0; i < g[pos].size(); i++){
// int to = g[pos][i].v, l = g[pos][i].l, t = g[pos][i].t;
// if(!vis[to]){
// vis[to] = true;
// int tmplen = length, tmptime = ttime;
// length += l;
// ttime += t;
// path.push_back(to);
// dfs_len(to);
// length = tmplen;
// ttime = tmptime;
// path.pop_back();
// vis[to] = false;
// }
// }
//} int ans_time = inf, num_for_mintime = inf;
int ttt, num;
//bool ti_ununique = false;
vector<int>mintime;
void dfs_time(int pos)
{
if(pos == ed){
if(num < num_for_mintime){
num_for_mintime = num;
mintime = path;
return;
}
}
for(int i = ; i < g[pos].size(); i++){
int to = g[pos][i].v;
if(!vis[to] && d_time[to] == d_time[pos] + g[pos][i].t){
vis[to] = true;
num++;
path.push_back(to);
dfs_time(to);
num--;
vis[to] = false;
path.pop_back();
}
}
}
//void dfs_time(int pos)
//{
// if(ttt > ans_time)return;
// if(pos == ed){
// if(ttt < ans_time || ttt == ans_time && num < num_for_mintime){
// ans_time = ttt;
// num_for_mintime = num;
// mintime = path;
//// if(ttt == ans_time)ti_ununique = true;
//// else ti_ununique = false;
// return;
// }
// }
// for(int i = 0; i < g[pos].size(); i++){
// int to = g[pos][i].v, t = g[pos][i].t;
// if(!vis[to]){
// vis[to] = true;
// num++;
// int tmptime = ttt;
// ttt += t;
// path.push_back(to);
// dfs_time(to);
// num--;
// path.pop_back();
// ttt = tmptime;
// vis[to] = false;
// }
// }
//} int main()
{
scanf("%d%d", &n, &m);
for(int i = ; i < m; i++){
int u, v;
int one_way;
int len, ti;
scanf("%d%d%d%d%d", &u, &v, &one_way, &len, &ti);
g[u].push_back(node(v, len, ti));
if(!one_way){
g[v].push_back(node(u, len, ti));
}
}
scanf("%d%d", &st, &ed); // memset(vis, 0, sizeof(vis));
// vis[st] = true;
// dfs_len(st);
// memset(vis, 0, sizeof(vis));
// vis[st] = true;
// path.clear();
// dfs_time(st); dijkstra();
memset(vis, , sizeof(vis));
dfs_len(st);
memset(vis, , sizeof(vis));
path.clear();
dfs_time(st);
ans_len = d_len[ed];
ans_time = d_time[ed]; if(mintime != minlen){
printf("Distance = %d: %d", ans_len, st);
for(int i = ; i < minlen.size(); i++){
printf(" -> %d", minlen[i]);
}
printf("\n");
printf("Time = %d: %d", ans_time, st);
for(int i = ; i < mintime.size(); i++){
printf(" -> %d", mintime[i]);
}
printf("\n");
}
else{
printf("Distance = %d; Time = %d: %d", ans_len, ans_time, st);
for(int i = ; i < minlen.size(); i++){
printf(" -> %d", minlen[i]);
}
printf("\n");
} return ;
}
