L3-007 天梯地图 （dijstra输出路径）

#include <iostream>
#include <vector>
using namespace std;
int map1[555][555];
int map2[555][555];
#define INF 0x3f3f3f3f
int dis1[555],dis2[555],dis3[555];
int vis[555];
int pre1[555],pre2[555];
int nds[555];
int n,m;
vector<int> vt1,vt2;
void dijstra1(int st)
{
for(int i=0;i<n;i++)
{
vis[i]=0;dis1[i]=INF;pre1[i]=i;nds[i]=0;
}
dis1[st]=0;
for(int i=0;i<n;i++)
{
int max1=INF;
int k=-1;
for(int j=0;j<n;j++)
{
if(!vis[j]&&dis1[j]<max1)
{
max1=dis1[j];
k=j;
}
}
if(k==-1) break;
vis[k]=1;
for(int j=0;j<n;j++)
{
if(!vis[j])
{
if(dis1[k]+map1[k][j]<dis1[j])
{
dis1[j]=dis1[k]+map1[k][j];
nds[j]=nds[k]+1;
pre1[j]=k;
}
else if(dis1[k]+map1[k][j]==dis1[j])
{
if(nds[j]>nds[k]+1)
{
nds[j]=nds[k]+1;
pre1[j]=k;
}
}
}
}
}
}
void dijstra2(int st)
{
for(int i=0;i<n;i++)
{
vis[i]=0;dis2[i]=INF;pre2[i]=i;dis3[i]=INF;
}
dis2[st]=0;
dis3[st]=0;
for(int i=0;i<n;i++)
{
int max1=INF;
int k=-1;
for(int j=0;j<n;j++)
{
if(!vis[j]&&dis2[j]<max1)
{
max1=dis2[j];
k=j;
}
}
if(k==-1) break;
vis[k]=1;
for(int j=0;j<n;j++)
{
if(!vis[j])
{
if(map2[k][j]+dis2[k]<dis2[j])
{
dis2[j]=map2[k][j]+dis2[k];
pre2[j]=k;
dis3[j]=map1[k][j]+dis3[k];
}
else if(map2[k][j]+dis2[k]==dis2[j])
{
if(map1[k][j]+dis3[k]<dis3[j])
{
dis3[j]=map1[k][j]+dis3[k];
pre2[j]=k;
}
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
map1[i][j]=map2[i][j]=INF;
}
for(int i=0;i<m;i++)
{
int x,y,w,l,t;
scanf("%d%d%d%d%d",&x,&y,&w,&l,&t);
if(!w)
{
map1[x][y]=map1[y][x]=l;
map2[x][y]=map2[y][x]=t;
}
else
{
map1[x][y]=l;
map2[x][y]=t;
}
}
int st,et;
scanf("%d%d",&st,&et);
dijstra1(st);
dijstra2(st);
int k1,k2;
k1=et;
vt1.push_back(et);
while(pre1[k1]!=k1)
{
vt1.push_back(pre1[k1]);
k1=pre1[k1];
}
k2=et;
vt2.push_back(et);
while(pre2[k2]!=k2)
{
vt2.push_back(pre2[k2]);
k2=pre2[k2];
}
int flag=1;
if(vt1.size()==vt2.size())
{
for(int i=0;i<vt1.size();i++)
{
if(vt1[i]!=vt2[i])
{
flag=0;
break;
}
}
}
else
flag=0;
if(flag)
{
printf("Time = %d; Distance = %d:",dis2[et],dis1[et]);
for(int i=vt1.size()-1;i>=0;i--)
{
if(i==vt1.size()-1)
printf(" %d",vt1[i]);
else printf(" => %d",vt1[i]);
}
}
else
{
printf("Time = %d:",dis2[et]);
for(int i=vt2.size()-1;i>=0;i--)
{
if(i==vt2.size()-1)
printf(" %d",vt2[i]);
else printf(" => %d",vt2[i]);
}
printf("n");
printf("Distance = %d:",dis1[et]);
for(int i=vt1.size()-1;i>=0;i--)
{
if(i==vt1.size()-1)
printf(" %d",vt1[i]);
else printf(" => %d",vt1[i]);
}
printf("n");
}
return 0;
}

最后

以上就是外向冬天为你收集整理的L3-007 天梯地图 （dijstra输出路径）的全部内容，希望文章能够帮你解决L3-007 天梯地图 （dijstra输出路径）所遇到的程序开发问题。

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