PTA 直捣黄龙（Dijkstra）_直捣黄龙pta

PTA直捣黄龙的题解

基本思路

一些记录数据的数据结构：

map<string,int> mmp1;
map<int,string> mmp2;   //映射据点名字和编号

int gra[205][205];  //存储图
int num[205];       //每个据点的敌人的数量
int tot[205];       //到达一据点，所能歼灭敌军的数量
int pth[205];       //到达一据点，最短路径的数量
int rot[205];       //记录路径
int tia[205];       //到达一据点，所解放的据点的总数
int dis[205];       //最短路
int vis[205];       //标记数组
1
2
3
4
5
6
7
8
9
10
11

在进行Dijkstra算法时，作一些适当的变形，即可解决问题：

if(dis[j] > dis[pres]+gra[pres][j]){     //找到更短的路径
    dis[j] = dis[pres]+gra[pres][j];     //更新最短路大小
    tot[j] = tot[pres]+num[j];           //记录歼灭敌军总数
    rot[j] = pres;                       //记录路径
    tia[j] = tia[pres]+1;                //经历据点数+1
    pth[j] = pth[pres];                  //传递最短路径数
}
else if(dis[j] == dis[pres]+gra[pres][j]){ //找到另一条最短路径
    pth[j]+= pth[pres];                    //更新最短路径数
    if(tia[j] < tia[pres]+1) {             //最短路不唯一，如果能解放更多的据点
        tia[j] = tia[pres]+1;              //更新经历的据点数
        rot[j]=pres;                       //记录路径
        tot[j] = tot[pres]+num[j];         //记录歼灭敌军总数
    }
    else if(tia[j] == tia[pres]+1){         //最短路和经历据点数都相同的路径不唯一
        if(tot[j] < tot[pres]+num[j]){      //如果能杀伤更多敌军
            rot[j]=pres;                    //记录路径
            tot[j] = tot[pres]+num[j];      //更新歼灭敌军数
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

整体算法如下：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int n,m;
string sta,ed;          //起点、终点
map<string,int> mmp1;
map<int,string> mmp2;   //映射据点名字和编号

int gra[205][205];  //存储图
int num[205];       //每个据点的敌人的数量
int tot[205];       //到达一据点，所能歼灭敌军的数量
int pth[205];       //到达一据点，最短路径的数量
int rot[205];       //记录路径
int tia[205];       //到达一据点，所解放的据点的总数
int dis[205];       //最短路
int vis[205];       //标记数组
//变形的Dijkstra算法
void dij() {
    for(int i=0;i<n;i++)
        dis[i]=gra[mmp1[sta]][i];
    for(int i=0;i<n;i++){
        int mins=INF;
        int pres=mmp1[sta];
        for(int j=0;j<n;j++){
            if(!vis[j] && dis[j]<mins){
                mins=dis[j];
                pres=j;
            }
        }
        if(mins>=INF) break;
        vis[pres]=1;
        for(int j=0;j<n;j++) {
            if(vis[j])
                continue;
            if(dis[j] > dis[pres]+gra[pres][j]){     //找到更短的路径
                dis[j] = dis[pres]+gra[pres][j];     //更新最短路大小
                tot[j] = tot[pres]+num[j];           //记录歼灭敌军总数
                rot[j] = pres;                       //记录路径
                tia[j] = tia[pres]+1;                //经历据点数+1
                pth[j] = pth[pres];                  //传递最短路径数
            }
            else if(dis[j] == dis[pres]+gra[pres][j]){ //找到另一条最短路径
                pth[j]+= pth[pres];                    //更新最短路径数
                if(tia[j] < tia[pres]+1) {             //最短路不唯一，如果能解放更多的据点
                    tia[j] = tia[pres]+1;              //更新经历的据点数
                    rot[j]=pres;                       //记录路径
                    tot[j] = tot[pres]+num[j];         //记录歼灭敌军总数
                }
                else if(tia[j] == tia[pres]+1){         //最短路和经历据点数都相同的路径不唯一
                    if(tot[j] < tot[pres]+num[j]){      //如果能杀伤更多敌军
                        rot[j]=pres;                    //记录路径
                        tot[j] = tot[pres]+num[j];      //更新歼灭敌军数
                    }
                }
            }
        }
    }
}

int main() {
    mmp1.clear();
    mmp2.clear();
    scanf("%d %d ",&n,&m);
    cin>>sta;
    cin>>ed;
    for(int i=0;i<205;i++){
        num[i]=0;
        rot[i]=-1;
        tot[i]=0;
        pth[i]=0;
        tia[i]=0;
        dis[i]=0;
        vis[i]=0;
        for(int j=0;j<205;j++){
            gra[i][j] = (i==j) ? 0 : INF;
        }
    }
    string uss,vss;
    mmp2[0]=sta;
    mmp1[sta]=0;
    for(int i=1;i<n;i++) {     
        cin>>vss;
        scanf(" %d ",&num[i]);
        mmp1[vss]=i;
        mmp2[i]=vss;
    }
    for(int i=0;i<m;i++){
        int cst;
        cin>>uss;
        cin>>vss;
        scanf("%d",&cst);
        gra[mmp1[uss]][mmp1[vss]]=gra[mmp1[vss]][mmp1[uss]]=cst;
    }
    pth[0]=1;
    dij();
    vector<int> ptan;
    ptan.clear();
    int sstp=mmp1[ed];
    while(sstp!=-1){
        ptan.push_back(sstp);
        sstp=rot[sstp];
    }
    int lp=ptan.size();
    for(int i=0;i<lp;i++){
        cout<<mmp2[ptan[lp-1-i]];
        printf("%s",(i==lp-1)?"\n":"->");
    }
    cout<<pth[mmp1[ed]]<<" "<<dis[mmp1[ed]]<<" "<<tot[mmp1[ed]]<<endl;
    system("pause");
    return 0;
}
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