问题 D: 最短路径

问题 D: 最短路径
[命题人 : 外部导入]
时间限制 : 1.000 sec 内存限制 : 32 MB

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

输入
输入包含多组测试数据。

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

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

输出
每组输出占两行。

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

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

样例输入 Copy
3 3 1 3
1 3 3
1 2 1
2 3 1
样例输出 Copy
2
1 2 3

分析:
该题是涉及多条最短路径的最短路径问题，由于要输出最短路径，pre定义成vector<int>型数组，在采用dfs遍历最短路径时考虑字典序问题，典型的Dijkstra+Dfs应用。
值得注意一点，据说这题可能会输入重复的边，所以用邻接表在codeup上只能拿50分，建议直接用邻接矩阵。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxv=1001;
const int inf=10000000;
struct node{
int v,weight;
};
vector<node>Adj[maxv] ;
bool vis[maxv];
int dis[maxv];
vector<int>pre[maxv];//记录路径 
//dijkstra算法
void dijkstra (int n,int s) {
fill(vis,vis+n+1,false);
fill(dis,dis+n+1,inf); //初始化dis和vis
dis[s] =0;//这里求零点到各点最短距离
for(int i=0;i<n;i++) //循环n次
{
int min=inf,u=-1;
for(int j=1;j<=n;j++)
//找最短距离点 ，这里可以用优先队列存储dis下标更快 
{
if(!vis[j]&&dis[j]<min)
{
u=j;
min=dis[j];
}
}
if(u==-1) return ;//没有找到 
vis[u] =true;//标记已经找到的u 
for(int j=0;j<Adj[u].size();j++) //更新dis 
{
int x=Adj[u][j].v;
if(!vis[x])
{
if(dis[u]+Adj[u][j].weight<dis[x]){
dis[x]=dis[u]+Adj[u][j].weight;
pre[x].clear();
pre[x].push_back(u);}
else if(dis[u]+Adj[u][j].weight==dis[x])
pre[x].push_back(u);
}
}
}
}
vector<int>path,temppath;
void dfs(int s,int t){
if(t==s){
temppath.push_back(t);
int k=1,a=path.size(),b=temppath.size();
if(a){
while(a>0&&b>0){
if(temppath[b--]>path[a--]){
k=0;break;
}
if(temppath[b]<path[a])break;
}
}
if(k)path=temppath;
temppath.pop_back();
return;
}
temppath.push_back(t);
for(int i=0;i<pre[t].size();i++)
{
dfs(s,pre[t][i]);
}
temppath.pop_back();
}
int main(){
int n,m,s,t;
int x,y,w;
node temp;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=0;i<m;i++){
scanf("%d%d%d",&x,&y,&w);
temp.weight=w;
temp.v=x;
Adj[y].push_back(temp);
temp.v=y;
Adj[x].push_back(temp);
}
dijkstra(n,s);
if(dis[t]==inf)printf("can't arriven");
else {
dfs(s,t);
printf("%dn",dis[t]);
for(int i=path.size()-1;i>=0;--i)printf("%d ",path[i]);}
return 0;
}

最后

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

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