HDOJ2066“一个人的旅行”

小灰灰 2022-05-19 02:08 156阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> Problem Description 虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。 &nbsp; Input 输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个； 接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=&lt;(a,b)&lt;=1000;a,b 之间可能有多条路) 接着的第T+1行有S个数，表示和草儿家相连的城市； 接着的第T+2行有D个数，表示草儿想去地方。 &nbsp; Output 输出草儿能去某个喜欢的城市的最短时间。 &nbsp; Sample Input 6 2 3 1 3 5 1 4 7 2 8 12 3 8 4 4 9 12 9 10 2 1 2 8 9 10 &nbsp; Sample Output 9 </td> 
 </tr> 
 </tbody> 
</table>

根据我的总结，dijsktra有多种形式：

1.  一个起点，一个终点；[https://blog.csdn.net/qq\_37241934/article/details/81111198][https_blog.csdn.net_qq_37241934_article_details_81111198]
2.  多个起点，一个终点；[https://blog.csdn.net/qq\_37241934/article/details/81117775][https_blog.csdn.net_qq_37241934_article_details_81117775]
3.  多个地点，多个终点；

无论是哪种形式都要转化为一个起点一个终点去计算。**这个题就是多源起点，多源终点**。**其转换方法是**（以样例为图）：

![70][]

### **其主要的算法模板是：** ###

void dijsktra(int n){
 int i,j;
 for(i=0;i<=n;i++)
 {
 Div[i]=a[0][i];
 vis[i]=0;
 }
 vis[0]=1;
 //Div[v0]=0;
 int minpox=0;
 for(i=0;i<=n;i++){
 int minINF=INF;
 for(j=0;j<=n;j++){
 if(!vis[j]&&Div[j]<minINF){
 minINF=Div[j];
 minpox=j;
 }
 }//选择离起点最近的点作为中间点 
 vis[minpox]=1;
 for(j=0;j<=n;j++){
 if(!vis[j]&&Div[j]>Div[minpox]+a[minpox][j])
 Div[j]=Div[minpox]+a[minpox][j];
 }
 }
 }

### **完整的代码是：** ###

#include<stdio.h>
 #include<iostream>
 #include<algorithm> 
 using namespace std;
 int Div[1002];
 int vis[1002];
 int a[1009][1009];
 int INF=30000;
 void dijsktra(int n){
 int i,j;
 for(i=0;i<=n;i++)
 {
 Div[i]=a[0][i];
 vis[i]=0;
 }
 vis[0]=1;
 //Div[v0]=0;
 int minpox=0;
 for(i=0;i<=n;i++){
 int minINF=INF;
 for(j=0;j<=n;j++){
 if(!vis[j]&&Div[j]<minINF){
 minINF=Div[j];
 minpox=j;
 }
 }//选择离起点最近的点作为中间点 
 vis[minpox]=1;
 for(j=0;j<=n;j++){
 if(!vis[j]&&Div[j]>Div[minpox]+a[minpox][j])
 Div[j]=Div[minpox]+a[minpox][j];
 }
 }
 }
 void chu(){
 	int i,j;
 	for(i=0;i<=1002;i++)
 {
 for(j=0;j<=1002;j++)
 {
 a[i][j]=INF;
 if(i==j)
 a[i][j]=0;
 }
 
 }
 }
 int main(){
 int T,S,D,i,j,p,q,t,w,v0,min,max;
 while(cin>>T>>S>>D){
 	min=1002;
 	max=0;
 chu(); 
 for(i=0;i<T;i++)
 {
 cin>>p>>q>>t;
 if(p>max)
 	max=p;
 	if(q>max)
 		max=q;//max则为最大的站点 
 if(a[p][q]>t||a[q][p]>t)//因为两个点之间有多条路，选择其中最短的一条 
 a[p][q]=a[q][p]=t;//看清楚题意是不是双向路 
 }
 max=max+1;
 for(i=0;i<S;i++)
 {
 scanf("%d",&v0);
 a[0][v0]=a[v0][0]=0;//把起点设置为0，则a[0][起点] 距离为0 
 }
 		 for(i=0;i<D;i++)
 {
 scanf("%d",&v0);
 a[max][v0]=a[v0][max]=0; //把终点设置成最大城市号+1=max，则max到输入的重点距离为0； 
 } 
 		 dijsktra(max);
 printf("%d\n",Div[max]);
 }
 return 0;
 }

[https_blog.csdn.net_qq_37241934_article_details_81111198]: https://blog.csdn.net/qq_37241934/article/details/81111198
[https_blog.csdn.net_qq_37241934_article_details_81117775]: https://blog.csdn.net/qq_37241934/article/details/81117775
[70]: /images/20220519/c73498a3ecfa4fd0ae626be706821bb5.png