PAT 1030

题目 ： Travel Plan

分值 ： 30
难度 ： Dijkstra
思路 ： 无非两层条件的Dijkstra,都是贪心的，所以可以一起解决
坑点 ： 打印路径时，用递归打印，注意头有没有打进去，别偷懒，path[i]设置为-1 保险
评语 ： 只要你写的正确一点，没什么边界可找麻烦

具体代码如下

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
#include <iostream>
#include <vector>
#define Max_ 999999999
using namespace std;
int Dict[501][501];
int Cost[501][501];
void init()
{
    for(int i = 0 ;i <501; i++)
        for(int j = 0 ; j < 501 ; j++)
            if(i!=j)
                Dict[i][j] = Cost[i][j] = Max_ ;
}
void print(vector<int> ans, int D)
{
    int cur =D ;
    if(cur !=-1)
    {
        print(ans, ans[cur]) ;
        cout << cur <<" ";
    }
}
int main()
{
    int N ,M ,S,D ,c1 ,c2 ,t,c;
    cin >> N >> M >> S >> D ;
    init();
    for(int i = 0 ;i< M ; i++)
    {
        cin >>c1>>c2>>t>>c ;
        Dict[c1][c2] =Dict[c2][c1]= t ;
        Cost[c1][c2] =Cost[c2][c1]= c ;
    }
    vector<int> dict(N,Max_) ;
    vector<int> cost(N,Max_) ;
    vector<int> path(N,-1) ;
    vector<bool> flag(N,false);
    int cur = 0 ;
    dict[S] = 0 ;
    cost[S] = 0 ;
    while(cur <N )
    {
        int min = Max_ , index ;
        for(int i = 0 ;i< N ; i++)
        {
            if(flag[i]) continue;
            if(dict[i] < min)
            {
                min = dict[i];
                index = i ;
            }
        }
        flag[index] = true ;
        for(int i = 0 ; i< N ; i++)
        {
            if(flag[i]) continue ;
            if(dict[i] > dict[index]+ Dict[index][i])
            {
                dict[i] = dict[index] + Dict[index][ i] ;
                cost[i] = cost[index] + Cost[index][i] ;
                path[i] = index ;
            }
            else if(dict[i] == dict[index]+ Dict[index][i] &&  cost[i] > cost[index] + Cost[index][i] )
            {
                cost[i] = cost[index] + Cost[index][i] ;
                path[i] = index;
            }
        }
        cur ++ ;
    }
    print(path ,D);
    cout << dict[D] <<" "<<cost[D]<<endl ;
}
Dfs 深搜+ 回溯
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
#include <iostream>
#include <vector>
#define Max_ 999999999
using namespace std;
vector<int> ans ;
vector<int> temp ;
vector<int> flag;
int Dict[501][501];
int Cost[501][501];
int Min_dict =Max_ , Min_cost =Max_ , N ,S,D;
void init()
{
    for(int i = 0 ;i <501; i++)
        for(int j = 0 ; j < 501 ; j++)
            if(i!=j)
                Dict[i][j] = Cost[i][j] = Max_ ;
}
void Dfs(int pos ,int dict , int cost)
{
    if(pos == D)
    {
        if(dict < Min_dict)
        {
            Min_dict = dict ;
            Min_cost = cost ;
            ans =temp;
        }else if( dict == Min_dict && cost<Min_cost )
        {
            Min_cost = cost ;
            ans = temp ;
        }
        return ;
    }
    for(int i = 0 ; i< N ; i++)
    {
        if(flag[i] || Dict[pos][i] ==Max_ || pos==i) continue ;
        flag[i] = true ;
        temp.push_back(i) ;
        Dfs(i ,dict+Dict[pos][i] , cost+Cost[pos][i]) ;
        flag[i] = false;
        temp.pop_back() ;
    }
}
int main()
{
    int M,c1 ,c2 ,t,c;
    cin >> N >> M >> S >> D ;
    flag.resize(N+1) ;
    init();
    for(int i = 0 ;i< M ; i++)
    {
        cin >>c1>>c2>>t>>c ;
        Dict[c1][c2] =Dict[c2][c1]= t ;
        Cost[c1][c2] =Cost[c2][c1]= c ;
    }
    flag[S] = true ;
    Dfs(S,0,0);
    cout << S ;
    for(int i = 0 ;i<ans.size() ;i++)
        cout <<" " <<ans[i];
    cout <<" "<<Min_dict <<" "<<Min_cost <<endl ;
}