PAT 1002

题目 ： All Roads Lead to Rome

分值 ： 30
难度 ： 中等题
思路 ： 给 N 个点,是字符串形式,第一步要做的就是把字符串映射成数字,我在这里利用了map
       然后就是最短路径多条件,先要求路径最短,再要求收益最高,再要求平均收益高,好在这
       里三个要求都是贪心可解决的,因此只要在判断路径是否更优上写个层次结构就行了.
坑点 ： 1）N个点是字符给出的,需要自己进行映射.
       2）判断路径是否更优,层次结构理清楚.
       3）然后判断cost相同的路经数如何更新:距离相同+=／距离不同= 中间点路经数
       4）利用pre数组记录各个点之前的那个点，打印时需要正向打印：利用递归体解决.
评分 ： 总的来说,不难但是细节很多,做下来让人感觉很充实,一遍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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <string>
#include <map>
#define MAX_ 99999999
using namespace std ;
map <string , int> dict ;
map <string , int>:: iterator iter ;
int happiness[201] ;
int cur = 0 ;
int data_map[201][201] ;
int pre[201] ;

void print( int x )
{
    if(x!=-1)
    {
        print(pre[x]);
        for(iter=dict.begin() ; iter!= dict.end() ;iter++)
            if(iter->second == x)
            {
                if(iter->second == dict["ROM"])
                {
                    cout<<iter->first<<endl ;
                    break;
                }
                cout<< iter->first <<"->" ;
                break ;
            }
    }
}
int main()
{
    int N , K ;
    string start ;
    cin >> N >> K >>start ;
    dict[start] = cur++ ;
    for(int i = 0 ; i<N ; i++)
        for(int j = 0 ; j < N ; j++)
            if( i!=j )
                data_map[i][j] = MAX_ ;
    for(int i = 0 ; i< N-1 ; i++ )
    {
        string temp ;
        int value ;
        cin >> temp >> value ;
        iter = dict.find( temp ) ;
        if(iter != dict.end() ) // find it
            happiness[iter->second] =value ;
        else
        {
            dict[temp] = cur++ ;
            happiness[ dict[temp] ] = value ;
        }
    }
    for(int i = 0 ; i< K ;i++)
    {
        string s1 ,s2 ;
        int cost ;
        cin >> s1 >> s2 >>cost ;
        data_map[ dict[s1] ] [ dict[s2] ] = cost ;
        data_map[ dict[s2] ] [ dict[s1] ] = cost ;
    }
    /*
     *     start find the path
     *
     */
    int dicts[N] ;
    int sum_happy[N] ;
    int sum_point[N] ;
    int flag[N] ;
    int route[N] ;

    for(int i = 0 ; i < N ; i++)
    {
        dicts[i] = MAX_ ;
        sum_happy[i] = 0 ;
        sum_point[i] = 0 ;
        flag[i] = 0 ;
        route[i] = 0 ;
        pre[i] = -1 ;
    }
    int count = 0 ;
    dicts[ dict[start] ] = 0 ;
    sum_point[ dict[start] ] = 0 ;
    sum_happy[ dict[start] ] = 0 ;
    route[ dict[start] ] = 1 ;
    while(count < N )
    {
        int min = MAX_ , index = 0 ;
        for(int i = 0 ; i< N ; i++)
        {
            if( !flag[i] && dicts[i] < min )
            {
                min = dicts[i];
                index = i ;
            }
        }
        flag[ index ] = 1 ;
        count ++ ;
        for(int i = 0 ; i< N ; i++)
        {
            if(flag[i])
                continue ;
            if( dicts[index] + data_map[index][i] < dicts[i])
            {
                route[i] = route[index] ;
                pre[i] = index ;
                dicts[i] = dicts[index] + data_map[index][i] ;
                sum_happy[i] = sum_happy[index] + happiness[i] ;
                sum_point[i] = sum_point[index] + 1 ;
            }
            else if(dicts[index] + data_map[index][i] == dicts[i])
            {
                route[i] += route[index] ;
                if( sum_happy[i] < sum_happy[index] + happiness[i]  )
                {
                    sum_happy[i] = sum_happy[index] + happiness[i];
                    sum_point[i] = sum_point[index] + 1 ;
                    pre[i] = index ;
                }
                else if( sum_happy[i] == sum_happy[index] + happiness[i] )
                {
                    if( sum_point[i] > sum_point[index] + 1 )
                    {
                        sum_point[i] = sum_point[index] +1 ;
                        pre[i] = index ;
                    }
                }
            }
        }
    }
    cout << route[ dict["ROM"]] <<" "<< dicts[ dict["ROM"]] <<" ";
    cout << sum_happy[ dict["ROM"]] <<" "<< sum_happy[ dict["ROM"]] / sum_point[ dict["ROM"]] <<endl;
    int temp = dict["ROM"] ;
    print(temp) ;
}