POJ1847 Tram ACM解题报告（dijkstra求最短路）

这题题意好难理解，看了别人写的题意才理解了，理解之后就是一个求最短路的简单题（我是新手，据说用bellman，floyd，spfa都可以做，我去学习下）

这题首先输入n个点和起点终点，

接下去是n个点，每个点有ki个方向，第一个输入的方向是可以不用转换就走的，可以记为map[i][j]=0，

接下去输入的ki-1个方向就是需要1次转换才能走，记为map[i][j]=1；

然后使用dijkstra或者其他算法的模板即可（我再去练练其他算法）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define INF 10000000
int map[105][105];
int v[105],d[105];
int main()
{
int n,a,b;
cin>>n>>a>>b;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) map[i][j]=INF;
}
for(int i=1;i<=n;i++)
{
int k,h;
cin>>k;
for(int j=1;j<=k;j++)
{
scanf("%d",&h);
if(j==1) map[i][h]=0;
else map[i][h]=1;
}
}
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++) d[i]=map[a][i];//各点到源点A的距离
for(int i=1;i<=n;i++)
{
int temp=INF,u;
for(int j=1;j<=n;j++)
{
if(!v[j]&&d[j]<temp)
{
u=j;
temp=d[j];
}
}
v[u]=1;
for(int j=1;j<=n;j++) d[j]=min(d[j],d[u]+map[u][j]);
}
if(d[b]==INF) printf("-1n");
else printf("%dn",d[b]);
return 0;
}

最后

以上就是现实冬日为你收集整理的POJ1847 Tram ACM解题报告（dijkstra求最短路）的全部内容，希望文章能够帮你解决POJ1847 Tram ACM解题报告（dijkstra求最短路）所遇到的程序开发问题。

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