Home PAT 1111 Online Map
Post
Cancel

PAT 1111 Online Map

Link

用两次 dijkstra, 第一次以距离为主权重, 时间为辅助权重; 第二次以时间为主权重, 路径上的节点个数为辅助权重.

注意最后输出的格式, 如果两种最短路径相等就需要合并输出. 路径用 vector 存储, 在判断时可以直接用 == 判断.

长时间没写 dijkstra 了, 忘记初始化 g 数组了… 要记得在输入路径之前把路径数组初始化为 INF !

还有, 如果程序陷入死循环了, 第一眼先看看是不是内层的 for 循环写成 for(int j=0;j<n;++i) 了…

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define N 510
int n,m,s,t;
int glen[N][N],gtime[N][N],dis[N],pre[N],cost[N];
bool v[N];
vector<int>ans1,ans2;
vector<int> Dijkstra(int g1[N][N],int g2[N][N],int &sum,int type){
    memset(dis,63,sizeof(dis));
    memset(v,false,sizeof(v));
    memset(cost,63,sizeof(cost));
    memset(pre,-1,sizeof(pre));
    dis[s]=0,cost[s]=0;
    for(int i=0;i<n;++i){
        int u=-1,minv=INF;
        for(int j=0;j<n;++j)
            if(!v[j]&&dis[j]<minv){
                minv=dis[j];
                u=j;
            }
        if(u==-1||u==t) break;
        v[u]=true;
        for(int j=0;j<n;++j){
            if(!v[j]){
                if(type==1){//cost用于记录time
                    if(dis[j]>dis[u]+g1[u][j]){
                        dis[j]=dis[u]+g1[u][j];
                        cost[j]=cost[u]+g2[u][j];
                        pre[j]=u;
                    }else if(dis[j]==dis[u]+g1[u][j]&&cost[j]>cost[u]+g2[u][j]){
                        cost[j]=cost[u]+g2[u][j];
                        pre[j]=u;
                    }
                }else{//cost用于记录intersection个数(不包括s)
                    if(dis[j]>dis[u]+g1[u][j]){
                        dis[j]=dis[u]+g1[u][j];
                        cost[j]=cost[u]+1;
                        pre[j]=u;
                    }else if(dis[j]==dis[u]+g1[u][j]&&cost[j]>cost[u]+1){
                        cost[j]=cost[u]+1;
                        pre[j]=u;
                    }
                }
            }
        }
    }
    sum=dis[t];
    vector<int>temp;
    int cur=t;
    while(cur!=s){
        temp.push_back(cur);
        cur=pre[cur];
    }
    return temp;
}
int main() {
    memset(glen,63,sizeof(glen));
    memset(gtime,63,sizeof(gtime));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int v1,v2,oneway,len,time;
        scanf("%d%d%d%d%d",&v1,&v2,&oneway,&len,&time);
        glen[v1][v2]=len,gtime[v1][v2]=time;
        if(!oneway) glen[v2][v1]=glen[v1][v2],gtime[v2][v1]=gtime[v1][v2];
    }
    scanf("%d%d",&s,&t);
    int sum1=0,sum2=0;
    ans1=Dijkstra(glen,gtime,sum1,1);
    ans2=Dijkstra(gtime,glen,sum2,2);
    if(ans1!=ans2){
        printf("Distance = ");
        printf("%d: %d",sum1,s);
        for(int i=ans1.size()-1;i>=0;--i)
            printf(" -> %d",ans1[i]);
        printf("\n");
        printf("Time = ");
        printf("%d: %d",sum2,s);
        for(int i=ans2.size()-1;i>=0;--i)
            printf(" -> %d",ans2[i]);
        printf("\n");
    }else{
        printf("Distance = %d; Time = %d: %d",sum1,sum2,s);
        for(int i=ans1.size()-1;i>=0;--i)
            printf(" -> %d",ans1[i]);
        printf("\n");
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.