#include<iostream>
using namespace std;
#include<algorithm>
int n, m;
int es[510][510], et[510][510], diss[510], dist[510], books[510], bookt[510];
#include<vector>
vector<int>temppath, path, temptime, timepath, pres[510], pret[510];
int start, jieshu;
const int inf = 99999999;
int minstime = inf;
int mincount = inf;
//求最短路径的dfs
void dfss(int v) {
temppath.push_back(v);
if (v == start) {
int stime = 0;
for (int i = temppath.size() - 1; i >= 1; i--) {
int id = temppath[i];
int nextid = temppath[i - 1];
stime += et[id][nextid];
}
if (stime < minstime) {
minstime = stime;
path = temppath;
}
}
for (int i = 0; i < pres[v].size() - 1; i++) {
dfss(pres[v][i]); **就是这里编译错误**
}
temppath.pop_back();
}
void dfst(int v) {
temptime.push_back(v);
if (v == start) {
int count = 0;
count = temptime.size() - 1;
if (count < mincount) {
mincount = count;
timepath = temptime;
}
}
for (int i = 0; i < pret[v].size() - 1; i++) {
dfst(pret[v][i]);
}
temptime.pop_back();
}
int main()
{
cin >> n, m;
fill(es[0], es[0] + 510 * 510, inf);
fill(et[0], et[0] + 510 * 510, inf);
fill(diss, diss + 510, inf);
fill(dist, dist + 510, inf);
//现在开始输入每个结点之间的距离和时间关系
int v1, v2, oneway, s, t;
for (int i = 0; i < m; i++) {
cin >> v1 >> v2 >> oneway >> s >> t;
if (oneway == 1)//说明是单行道
{
es[v1][v2] = s;
et[v1][v2] = t;
}
else if (oneway == 0)//说明是双行道
{
es[v1][v2] = s;
es[v2][v1] = s;
et[v1][v2] = t;
et[v2][v1] = t;
}
}
//现在输出起始点
cin >>start >> jieshu;
//先从最短路径开始搞起
diss[start] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
int minn = inf;
for (int j = 0; j < n; j++) {
if (books[j] == 0 && diss[j] < minn) {
minn = diss[j];
u = j;
}
}
if (u == -1) {
break;
}
books[u] = 1;
for (int v = 0; v < n; v++) {
if (books[v] == 0 && es[u][v] != inf) {
if (diss[v] > diss[u] + es[u][v]) {
diss[v] = diss[u] + es[u][v];
pres[v].clear();
pres[v].push_back(u);
}
else if (diss[v] == diss[u] + es[u][v]) {
pres[v].push_back(u);
}
}
}
}
//现在开始dfs求最短路径
dfss(jieshu);
//现在开始求最短时间
dist[start] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
int minn = inf;
for (int j = 0; j < n; j++) {
if (bookt[j] == 0 && dist[j] < minn) {
minn = dist[j];
u = j;
}
}
if (u == -1) {
break;
}
bookt[u] = 1;
for (int v = 0; v < n; v++) {
if (bookt[v] == 0 && et[u][v] != inf) {
if (dist[v] > dist[u] + et[u][v]) {
dist[v] = dist[u] + et[u][v];
pret[v].clear();
pret[v].push_back(u);
}
else if (dist[v] == dist[u] + et[u][v]) {
pret[v].push_back(u);
}
}
}
}
//现在dfs
dfst(jieshu);
//现在判断最短路径和最短时间的是不是同一个
int index = 1;
for (int i = 0; i < path.size() - 1; i++) {
if (path[i] == timepath[i]) {
index = 0;
}
}
if (index == 1)//说明两条路不相等
{
cout << "Distance = " << diss[jieshu] << ": " << start;
for (int i = path.size() - 2; i >= 0; i--) {
cout << "->" << path[i];
}
cout << endl;
cout << "Time = " << dist[jieshu] << ": "<<start;
for (int i = timepath.size() - 2; i >= 0; i--) {
cout << "->" << timepath[i];
}
}
else if (index == 0) {
cout << "Distance =" << diss[jieshu] << ": " << "Time = " << dist[jieshu] << ": "<<start;
for (int i = path.size() - 2; i >= 0; i--) {
cout << "->" << path[i];
}
}
cout << endl;
system("pause");
return 0;
}