B. wzy的大冒险——出发咯QAQ
单点时限: 2.0 sec
内存限制: 512 MB
wzy踏上了冒险的旅程。
现在他从地精手里买了一份地图,地图上有n个城镇。
他从第一个城镇出发,走向(没钱只能走)第n个城镇,现在,请你帮wzy找到一条最短的路径,并倒序(从n到1)输出一条最短路径。
举个栗子:如果有两条路径6 4 3 1和6 5 2 1,我们选择6 4 3 1这条。
地精小提示:路是单向的QAQ。
输入格式
第一行两个数n,m ,(1≤n≤103,1≤m≤103)
接下来m行,每行三个数x,y,z,表示点 x 与点 y 之间有一条权值为 z 的有向边 (1≤x,y,z≤103).
输出格式
第一行一个整数表示 1 到 n 的最短距离;
第二行倒序输出这条路径。
样例
input
5 7 1 2 69 1 3 87 1 4 79 2 5 94 2 3 10 3 5 79 4 5 43
output
122 5 4 1
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int cost[N][N]; // 存图
int used[N]; // 标记边是否用过
int dis[N]; // 起点到其他点的最短距离
int prevs[N]; // 存最短路上每个点的前驱点
int n, m;
void djk(int s)
{
memset(used, 0, sizeof(used));
memset(dis, 0x3f, sizeof(dis));
memset(prevs, -1, sizeof(prevs));
dis[s] = 0;
while(1)
{
int v = -1;
for(int i=1; i <= n; i++)
{
if(!used[i] && (v == -1 || dis[i] < dis[v]))
v = i;
}
if(v == -1) break;
used[v] = 1;
for(int i=1; i <= n; i++)
{
if(dis[i] > dis[v] + cost[v][i])
{
dis[i] = dis[v] + cost[v][i];
prevs[i] = v; // 保存最短路上下一个节点的前驱
}
}
}
}
vector<int> get_path(int t) // 得到的最短路是逆序的
{
vector<int> path;
for( ; t != -1; t = prevs[t])
path.push_back(t);
return path;
}
int main()
{
while(scanf("%d %d", &n, &m) != EOF)
{
memset(cost, INF, sizeof(cost));
int a, b, c;
for(int i=0; i<m; i++)
{
scanf("%d %d %d", &a, &b, &c);
cost[a][b] = c;
// cost[b][a] = c; // 如果边是双向的就加入
}
djk(1);
vector<int> ve = get_path(n);
int len = ve.size();
printf("%d\n", dis[n]);
for(int i=0; i<len; i++)
{
printf("%d%c", ve[i], i == len-1 ? '\n' : ' ');
}
}
return 0;
}