和1018思路如出一辙，先求最短路径，再dfs遍历
#include <iostream>
#include <cstdio>
#include <vector>
#include<algorithm>
using namespace std;
int e[][], c[][];// distence cost
vector<int> pre[];//到达当前节点的前一个节点
vector<vector<int> > st; //最短距离的路径
vector<int> path, tmppath;
int inf = ;
int mincost = inf;
int totalcost = ;
int S;//由于dfs 要用到这个变量，所以从main里提前 出发城市
void dfs(int node, int front)
{
tmppath.push_back(node);
int xx;
if (front == -)
{
xx = ;
}
else
{
xx = c[node][front];
}
totalcost += xx;
if (node == S)
{
if (totalcost < mincost)
{
mincost = totalcost;
path.clear();
path = tmppath;
}
totalcost = totalcost - xx;
tmppath.pop_back();
return;
}
for (int i = ; i < pre[node].size(); i++)
{
dfs(pre[node][i], node);
}
totalcost = totalcost - xx;
tmppath.pop_back();
} int main()
{
int N, M, D;
int a, b, tmp1, tmp2;
fill(e[], e[] + * , inf);
fill(c[], c[] + * , inf);
scanf("%d%d%d%d", &N, &M, &S, &D);
for (int i = ; i < M; i++)
{
scanf("%d%d", &a, &b);
scanf("%d", &tmp1);
e[a][b] = e[b][a] = tmp1;
scanf("%d", &tmp2);
c[a][b] = c[b][a] = tmp2;
} //输入结束
//Dijkstra
int dis[];
int mark[];
fill(mark, mark + , );
fill(dis, dis + , inf);
dis[S] = ;
pre[S].push_back(S);
int point, near;//当前选择要加入的点 和 最近
for (int i = ; i < N; i++)
{
point = -, near = inf;
for (int j = ; j < N; j++)
{
if (mark[j] == && dis[j] < near)
{
point = j;
near = dis[j];
}
}
if (near == inf)break;//所有可达点都已加入
mark[point] = ;
for (int j = ; j < N; j++)
{
if (dis[j] > dis[point] + e[point][j])
{
dis[j] = dis[point] + e[point][j];
pre[j].clear();
pre[j].push_back(point);
}
else if (dis[j] == dis[point] + e[point][j])
{
pre[j].push_back(point);
}
} }
dfs(D, -);//pre存的是到当前节点的前一个节点，所以要倒回去
if(path.size()>)
for (int i = path.size() - ; i >= ; i--)
{
printf("%d ", path[i]);
}
else
printf("%d",S);
printf("%d %d", dis[D], mincost);
return ; }