首页 > 代码库 > hdu 2680 Choose the best route

hdu 2680 Choose the best route

2024-07-11 17:19:02   223人阅读

Choose the best route

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6501    Accepted Submission(s): 2147


Problem Description
One day , Kiki wants to visit one of her friends. As she is liable to carsickness , she wants to arrive at her friend’s home as soon as possible . Now give you a map of the city’s traffic route, and the stations which are near Kiki’s home so that she can take. You may suppose Kiki can change the bus at any station. Please find out the least time Kiki needs to spend. To make it easy, if the city have n bus stations ,the stations will been expressed as an integer 1,2,3…n.
 

 

Input
There are several test cases. 
Each case begins with three integers n, m and s,(n<1000,m<20000,1=<s<=n) n stands for the number of bus stations in this city and m stands for the number of directed ways between bus stations .(Maybe there are several ways between two bus stations .) s stands for the bus station that near Kiki’s friend’s home.
Then follow m lines ,each line contains three integers p , q , t (0<t<=1000). means from station p to station q there is a way and it will costs t minutes .
Then a line with an integer w(0<w<n), means the number of stations Kiki can take at the beginning. Then follows w integers stands for these stations.
 

 

Output
The output contains one line for each data set : the least time Kiki needs to spend ,if it’s impossible to find such a route ,just output “-1”.
 

 

Sample Input
5 8 51 2 21 5 31 3 42 4 72 5 62 3 53 5 14 5 122 34 3 41 2 31 3 42 3 211
 

 

Sample Output
1-1
 

 

       题意：一个人要到他的朋友家去，有n个站台，有m个可以从p到q的车次，有方向的，而且给出他的的朋友家在那个车站。给出几个他家附近的车站，要你求最短的那个一个达到要多久，若不能到达则输出-1.

      解题思路：如果我们直接从他家附近的车站一个一个来找最短的肯定就要超时，我们换一个思路，把终点当做起点，然后找从终点到各个点的距离，但它是有向图，所以在输入的时候，我们要把从p到q的距离，改成从q到p的距离就好了，而且这里又有一个坑，就是它从一个点到另一个点不止一条路，取最短的哪一个。

 

贴出代码:

 

#include <stdio.h>#define maxn 0x3f3f3f3fint map[1005][1005], dis[1005], visited[1005];void Dijkstra(int start, int n)     //最短路的模板{    int mind;    int pre = start;    for(int i = 1; i<=n; i++)    {        dis[i] = map[start][i];        visited[i] = 0;    }    visited[start] = 1;    for(int i = 1; i<=n; i++)    {        mind = maxn;        for(int j = 1; j<=n; j++)        {            if(mind > dis[j] && !visited[j])            {                mind = dis[j];                pre = j;            }        }        visited[pre] = 1;        for(int j = 1; j<=n; j++)        {            if(dis[j] > dis[pre]+map[pre][j] && !visited[j])                dis[j] = dis[pre]+map[pre][j];        }    }}int main(){    int n, m, k, start, finish;    int x, y, vaule, mind;    while(scanf("%d%d%d", &n, &m, &finish)!=EOF)    {        for(int i = 1; i<=n; i++)     //进行初始化        {            for(int j = 1; j<=n; j++)            {                    map[i][j] = maxn;            }        }        while(m--)        {            scanf("%d%d%d", &x, &y, &vaule);            if(map[y][x] > vaule)            {                map[y][x] = vaule;           //改变他们的指向，为后面做好准备，并要最短的那一条路            }        }        mind = maxn;        scanf("%d", &k);        Dijkstra(finish, n);           //查找终点到各个点的距离        for(int i = 1; i<=k; i++)        {            scanf("%d", &start);            if( mind > dis[start])                mind = dis[start];        }        if(mind != maxn)            printf("%d\n", mind);        else            printf("-1\n");    }    return 0;}

 


联系
我们