首页 > 代码库 > nefu-1297 表哥的旅行（最短路问题）
nefu-1297 表哥的旅行（最短路问题）
题目链接：
http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=1197
注意事项：
1.初始数组长度为零
2.同样路径可能花费不同的时间
3.运用变形的Dijkstra算法
代码思路：
先初始化二维数组e和cot再输入数据并更新二维数组e和最大的cot，接着输入能到达的点fly并把e[fly][0]和e[0][fly]初始化为0，最后输入想要到达的f，然后运用Dijkstra算法得出到达各点的最短路数组，最后找出最短路数组的最小值ans。
代码如下：
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #define inf 1<<30 6 using namespace std; 7 8 int e[1205][1205]; 9 int a,b,t,n,m,l,cot,ans,fly[1205],f[1205],book[1205],dis[1205];10 int dsj()11 {12 int u,pos;13 memset(book,0,sizeof(book));14 book[0]=1;15 for(int i=0;i<=cot;i++)16 dis[i]=e[i][0];17 for(int i=1;i<=cot;i++)18 {19 pos=inf;20 for(int j=1;j<=cot;j++)21 {22 if(dis[j]<pos&&book[j]==0)23 {24 pos=dis[j];u=j;25 }26 }27 book[u]=1;28 for(int v=1;v<=cot;v++)29 {30 if(!book[v]&&dis[v]>dis[u]+e[u][v])31 dis[v]=dis[u]+e[u][v]; 32 }33 }34 return 0;35 }36 int main()37 {38 while(~scanf("%d%d%d",&n,&m,&l))39 {40 cot=0;41 for(int i=0;i<1111;i++)42 {43 for(int j=0;j<1111;j++)44 e[i][j]=inf;45 e[i][i]=0;46 }47 for(int i=0;i<n;i++)48 {49 scanf("%d%d%d",&a,&b,&t);50 if(t<e[a][b])51 e[a][b]=e[b][a]=t;52 if(cot<a||cot<b)53 cot=a>b?a:b;54 }55 for(int i=0;i<m;i++)56 {57 scanf("%d",&fly[i]);58 e[fly[i]][0]=e[0][fly[i]]=0;59 }60 for(int i=0;i<l;i++)61 scanf("%d",&f[i]);62 dsj();63 ans=inf;64 for(int i=0;i<l;i++)65 if(ans>dis[f[i]])66 ans=dis[f[i]];67 if(ans==inf)68 printf("NO\n");69 else70 printf("%d\n",ans);71 }72 return 0;73 }
nefu-1297 表哥的旅行（最短路问题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。