Codeup100000621问题 D: 最短路径

题目描述：

有n个城市m条道路（n<1000, m<10000)，每条道路有个长度，请找到从起点s到终点t的最短距离和经过的城市名。

输入：

输入包含多组测试数据。

每组第一行输入四个数，分别为n，m，s，t。

接下来m行，每行三个数，分别为两个城市名和距离。

输出：

每组输出占两行。

第一行输出起点到终点的最短距离。

第二行输出最短路径上经过的城市名，如果有多条最短路径，输出字典序最小的那条。若不存在从起点到终点的路径，则输出“can’t arrive”。

样例输入：

3 3 1 3
1 3 3
1 2 1
2 3 1

样例输出：

2
1 2 3

实现代码：

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1010;
const int INF = 0x3fffffff;
bool vis[maxn];
int n, d[maxn], G[maxn][maxn], pre[maxn];
struct node {
int v, w;
node(int x, int y): v(x), w(y) { };
};
vector<node> adj[maxn];
void Dijkstra(int s, int t) {
fill(d, d + maxn, INF);
fill(vis, vis + maxn, false);
for(int i = 1; i <= n; ++i) {
pre[i] = i;
}
d[s] = 0;
for(int i = 1; i <= n; ++i) {
int min = INF, u = -1;
for(int j = 1; j <= n; ++j) {
if(d[j] < min && vis[j] == false) {
u = j;
min = d[j];
}
}
if(u == t) {
return;
}
if(u == -1) {
return;
}
vis[u] = true;
for(int j = 0; j < adj[u].size(); ++j) {
int v = adj[u][j].v;
if(vis[v] == false) {
if(d[u] + adj[u][j].w < d[v]) {
d[v] = d[u] + adj[u][j].w;
pre[v] = u;
} else if(d[u] + adj[u][j].w == d[v] && u < pre[v]) {
pre[v] = u;
}
}
}
}
}
void DFS(int v, int s) {
if(v == s) {
printf("%d", v);
return ;
}
DFS(pre[v], s);
printf(" %d", v);
}
int main() {
int m, s, t, d1, d2, w;
while(~scanf("%d %d %d %d", &n, &m, &s, &t)) {
for (int i = 0; i <= n; ++i) {
adj[i].clear();
}
for(int i = 0; i < m; ++i) {
scanf("%d %d %d", &d1, &d2, &w);
adj[d1].push_back(node(d2, w));
adj[d2].push_back(node(d1, w));
}
Dijkstra(s, t);
if(d[t] == INF) {
printf("can't arriven");
} else {
printf("%dn", d[t]);
DFS(t, s);
printf("n");
}
}
return 0;
}
// 此题没说编号范围所以有可能不是连续编号，所以用邻接表存储合理，邻接矩阵会出错

最后

以上就是标致小霸王为你收集整理的Codeup100000621问题 D: 最短路径的全部内容，希望文章能够帮你解决Codeup100000621问题 D: 最短路径所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。