PAT 1087

题目 ： All Roads Lead to Rome

分值 ： 30
难度 ： 中等题
思路 ： Dijkstra
坑点 ： 因为输入数据是string类型,需要一个string -> int 的映射,我用了map
       也用了 另一个 int -> string 映射回来,一次AC没有超时很开心了！

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <map>
#define  MAX_ 999999999
using namespace std;
map <string ,int > db ;
map <int , string > db2;
map <string, int >::iterator iter;
int happiness[202] ;
int Map[202][202] ;
int pre[202];
int cur = 0 ;
void print(int a)
{
    if(pre[a]!=-1)
    {
        print(pre[a]);
        cout <<"->"<<db2[a];
    }
}
int main() {
    int N , K ,value;
    string start ;
    cin >> N >> K  >>start;
    for(int i = 0 ; i< N ;i++)
        for(int j = 0 ; j< N  ; j++)
            if(i!=j)
                Map[i][j] = MAX_;
    db[start] = cur ++;
    db2[0] = start;
    string temp ;
    for(int i = 0 ; i< N-1 ; i++)
    {
        cin >> temp >> value;
        db[temp] = cur ;
        db2[cur] = temp;
        happiness[cur++] = value ;
    }
    string s1 ,s2 ;
    int v1 ,v2 ,cost ;
    for(int i = 0 ; i< K ; i++)
    {
        cin >>s1 >>s2 >>cost;
        Map[db[s1]][db[s2]] = cost;
        Map[db[s2]][db[s1]] = cost;
    }
    int dict[N] ,flag[N] , sum[N],total[N], path[N];
    for(int i = 0 ; i< N ; i++)
    {
        dict[i] =MAX_ ;
        flag[i] = 0 ;
        sum[i] = 0;
        total[i] = 0 ;
        pre[i] = -1 ;
        path[i] = 1;
    }
    int count = 0 ;
    dict[db[start]]  = 0 ;
    int min ,index ;
    while (count < N )
    {
        min = MAX_ ;
        for(int i = 0 ; i< N ; i++)
        {
            if(flag[i])continue;
            if(dict[i] < min )
            {
                min = dict[i] ;
                index = i ;
            }
        }
        flag[index] = 1 ;
        for(int i = 0 ; i< N ; i++)
        {
            if(flag[i])continue;
            if(Map[index][i] +dict[index] < dict[i])
            {
                dict[i] = Map[index][i] +dict[index] ;
                sum[i] = sum[index] + happiness[i];
                total[i] = total[index] +1 ;
                path[i] = path[index] ;
                pre[i] = index;
            }
            else if(Map[index][i] +dict[index] == dict[i])
            {
                path[i] += path[index] ;
                if(sum[i] < sum[index] + happiness[i])
                {
                    sum[i] = sum[index] + happiness[i];
                    total[i] = total[index] +1 ;
                    pre[i] = index;
                }
                else if(sum[i] == sum[index] + happiness[i])
                {
                    if( total[i] > total[index] +1 )
                    {
                        total[i] =total[index] +1 ;
                        pre[i] = index;
                    }
                }
            }
        }
        count ++ ;
    }
    cout << path[db["ROM"]]<<" "<<dict[db["ROM"]] <<" "<<sum[db["ROM"]]<<" "<<sum[db["ROM"]]/total[db["ROM"]]<<endl ;
    cout <<start;
    print(db["ROM"]) ;
}