PAT 1072

题目 ： Gas Station

分值 ： 30
难度 ： 中等题
思路 ： 对于每个可能的Gas位置做一次Dijkstra，然后对于每次出来的dict数组进行处理
坑点 ： 一开始的时候,在Dijkstra内部寻找最小的dict[i] 时,我忘记了去判断节点是否被访问
       过,以至于在寻找最近节点时会重复找最开始的dict[start],使Dijkstra无法正常迭代.
       更正之后,一次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
#include <iostream>
using namespace std ;
#define MAX_ 99999999 ;
int Map[1020][1020];
int result[11] ;
int small[11] ;
int chose[11];

int N ;
int change(string s)
{
    int value= 0 ;
    if(s[0] == 'G')
    {
        for(int i = 1; i < s.size();i++)
            value = value*10 + s[i]-'0' ;
        return N + value ;
    }
    else
    {
        for(int i = 0; i < s.size();i++)
            value = value*10 + s[i]-'0' ;
        return value ;
    }
}
int main() {
    int M ,K,Ds ;
    cin >> N >> M>>K >>Ds;
    for(int i = 1 ; i<= N+M ; i++)
        for(int j = 1  ; j<= N+M ;j++)
            if(i!=j)
                Map[i][j] =MAX_;
    for(int i = 0; i<K ;i++)
    {
        string s1 ,s2;
        int cost,v1,v2;
        cin >> s1 >>s2 >>cost ;
        v1 = change(s1);
        v2 = change(s2);
        Map[v1][v2] = cost;
        Map[v2][v1] = cost;
    }
    for(int i = N+1 ; i<= N+M ; i++)
    {
        int dict[N+M ];
        int flag[N+M ];
        int count = 0 ;
        for(int j = 1; j<=N+M ;j++)
        {
            dict[j] = MAX_ ;
            flag[j] = 0;
        }
        int min , index;
        dict[i] = 0 ;
        count = 0;
        while(count <=N+M)
        {
            min = MAX_ ;
            for(int j = 1 ; j <= N+M ; j++)   //每次找出最小的 dict[i]
            {
                if(!flag[j] && dict[j] < min)
                {
                    min = dict[j] ;
                    index = j;
                }
            }
            flag[index] =1 ;
            count ++ ;

            for(int j = 1 ;j<=N+M ;j++)
            {
                if(flag[j]) continue;  //如果j访问过 直接下一个点
                if(dict[index] + Map[index][j]  < dict[j])
                {
                    dict[j] = dict[index] + Map[index][j] ;
                }
            }
        }
        min = MAX_ ;
        int sum = 0 ;
        int cur = i-N ;
        int FLAG = 0 ;
        for(int j =1 ; j<= N ;j++)
        {
            sum += dict[j] ;
            if(dict[j] < min)
                min = dict[j] ;
            if(dict[j] >Ds )
            {
                FLAG =1 ;
                break ;
            }
        }
        if(!FLAG)
        {
            chose[cur]=1 ;
            result[cur] =sum ;
            small[cur] =min ;
        }
    }
    int max = 0 ,sum ;
    int index = 0  ;

    for(int i= 1 ; i<= M ; i++ )
    {
        if(!chose[i]) continue;
        if(small[i] > max)
        {
            max =small[i] ;
            index = i ;
            sum = result[i] ;
        }
        if(small[i] ==max && result[i]< sum)
        {
            sum =result[i];
            index = i ;
        }
    }
    if(index !=0)
    {
        cout << "G"<<index<<endl ;
        printf("%.1lf %.1lf\n",1.0*max , 1.0*sum/N);
    }
    else cout <<"No Solution"<<endl;
}