Til the Cows Come Home

小鱼儿 2022-05-24 01:09 123阅读 0赞

Problem Description：

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible.  
Farmer John's field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it.

Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.

Input：

\* Line 1: Two integers: T and N <br> <br>\* Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.

Output：

\* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.

Sample Input：

5 5  
1 2 20  
2 3 30  
3 4 20  
4 5 20

1 5 100

Sample Output：

题意：Bessie想要尽可能的多睡会儿觉，因此，Bessie走回仓库的距离要最短，即Bessie要走能到达仓库的最短路径，输入有多组测试，第一行是一个T和一个N，T代表有T条路径，N代表有N个地标（地标1是仓库），接下来的T行每行有3个数，分别是a，b，c，代表的是地标a到地标b的双向路径是c。求Bessie从n到1的最小距离。

思路：这道题是最短路的思想，用迪杰斯特拉（Dijkstra）的算法，求出源点1到各个点的最小距离，最后输出1到n的距离就是Bessie从n到1的最小距离。

My DaiMa：

#include<stdio.h>
    #include<iostream>
    using namespace std;
    const int MA = 9999999;
    int n,m,flag[1000],d[1000],dis[1000][1000],minn;
    int Dij()//Dijkstra算法
    {
        int k;
        for(int i = 1;i < m;i++)//此循环先找到源点仓库能到达哪些地标
            d[i] = dis[0][i];
        for(int i = 1;i < m;i++){
            minn=MA;
            for(int j = 1;j < m;j++){ //这个是用来找出目前最短路径的是哪个点
                if(flag[j]==0&&d[j]<minn){
                    k = j;//保存该地标
                    minn = d[j];
                }
            }
            flag[k] = 1;//标记该地标
            for(int j = 1;j < m;j++){
                if(flag[j]==0&&d[j]>d[k]+dis[k][j])//更新一些还可以优化的路径
                    d[j] = d[k]+dis[k][j];
            }
        }
        return d[m-1];
    }
    int main()
    {
        int a,b,c;
        while(~scanf("%d%d",&n,&m)){
            for(int i=0;i<m;i++){
                for(int j=0;j<m;j++)
                    dis[i][j]=MA;
                dis[i][i]=0;//如果是这样定义的话const int MA=0x3f3f3f3f，辣么就可以直接用memset函数赋初始值咧
                d[i]=MA;
                flag[i]=0;
            }
            for(int i=1;i<=n;i++){
                scanf("%d%d%d",&a,&b,&c);
                if(dis[a-1][b-1]>c)//为啥要比较，是因为可能输入中a到b有多条路径，而我们需要的是其中最短的距离，这点儿很重要
                    dis[a-1][b-1]=dis[b-1][a-1]=c;
            }
            printf("%d\n",Dij());
        }
        return 0;
    }