hdu 2066 一个人的旅行(裸dijkstra)-白红宇

hdu 2066 一个人的旅行(裸dijkstra)

阅读量：5089 次

发布时间：2019-06-13

本文共 1813 字，大约阅读时间需要 6 分钟。

题目描述：求s个点到d个点的最短路

Input

输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；

接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)

接着的第T+1行有S个数，表示和草儿家相连的城市；

接着的第T+2行有D个数，表示草儿想去地方。

Output

输出草儿能去某个喜欢的城市的最短时间。

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

Sample Output

_______________________________________________________

题解：

对s个点直接dijkstra就ok (dijkstra：从某一点开始 n次找点 n次更新路径寻找最短路)

#include <stdio.h>

#include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define LL long long#define _LL __int64using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1100;int Map[maxn][maxn];int t,s,d;int ss[maxn],dd[maxn];int n;int dis[maxn];int vis[maxn];void dijkstra(int src) { memset(dis,INF,sizeof(dis)); memset(vis,0,sizeof(vis)); vis[src] = 1; for(int i = 1; i <= n; i++) dis[i] = Map[src][i]; dis[src] = 0; for(int i = 1; i <= n; i++) { int Min = INF,pos; for(int j = 1; j <= n; j++) { if(!vis[j] && dis[j] < Min) { Min = dis[j]; pos = j; } } vis[pos] = 1; for(int j = 1; j <= n; j++) { if(!vis[j] && dis[j] > dis[pos] + Map[pos][j]) dis[j] = dis[pos] + Map[pos][j]; } }}int main() { while(~scanf("%d %d %d",&t,&s,&d)) { n = -1; memset(Map,INF,sizeof(Map)); int u,v,w; for(int i = 0; i < t; i++) { scanf("%d %d %d",&u,&v,&w); if(Map[u][v] > w) Map[u][v] = Map[v][u] = w; n = max( max(u,v),n ); } for(int i = 0; i < s; i++) scanf("%d",&ss[i]); for(int i = 0; i < d; i++) scanf("%d",&dd[i]); for(int i = 1; i <= n; i++) Map[i][i] = 0; int ans = INF; for(int i = 0; i < s; i++) { dijkstra(ss[i]); for(int j = 0; j < d; j++) ans = min(ans,dis[dd[j]]); } printf("%d\n",ans); } return 0;}

转载于:https://www.cnblogs.com/lhsghhqgmzy/p/10724029.html

你可能感兴趣的文章