第六章 图论 8 AcWing 1624. 地铁地图

第六章 图论 8 AcWing 1624. 地铁地图

原题链接

AcWing 1624. 地铁地图

算法标签

图论 单源最短路 dijkstra spfa

思路

若采用邻接矩阵存储

超出本题空间限制，因此无法采用邻接矩阵存储，可采用邻接表存储
若采用常规建图方式（即相邻两点之间建一条边）

采用另一种建图方式 若两点可达 建立双向边

最多需要建立边数

对于最短路问题 通常可存储的边数与点数


若采用常规dijkstra，算法时间复杂度O(n*m)，由于时间限制：0.4s，将会超时

因此采用堆优化版dijkstra(常规dijkstra瓶颈在于寻找最小值的点，堆优化版dijkstra将所有未寻找放置堆中，堆中寻找最小值时间复杂度为O(log(1)，更新最小值时间复杂度为O(log(n))，算法时间复杂度O(m*log(n))，由于时间限制：0.4s，可通过

由于可能会存在回路，对于回路，路径长度

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include
#define int long long
#define x first
#define y second
#define ump unordered_map
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
typedef pair PII;
const int N = 10005;
//int t, n, m, cnt, ans;
string info[N];
int h[N], ne[N*100], e[N*100], w[N*100], line[N*100], stop[N], dist[N], cnt[N], pre[N], idx;
bool st[N];
int n, m;
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
} 
string format(int x){
    char res[5];
    sprintf(res, "%04lld", x);
    return res;
}
void add(int a, int b, int c, int id){
    e[idx]=b, w[idx]=c, line[idx]=id, ne[idx]=h[a], h[a]=idx++;
}
void dij(int S, int T){
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0x3f, sizeof cnt);
    memset(st, 0, sizeof st);
    pq, greater> heap;
    heap.push({0, S});
    dist[S]=cnt[S]=0;
    while(heap.size()){
        auto t=heap.top();
        heap.pop();
        int val=t.y;
        if(val==T){
            break;
        }
        if(st[val]){
            continue;
        }
        st[val]=true;
        for(int i=h[val]; ~i; i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[val]+w[i]){
                dist[j]=dist[val]+w[i];
                cnt[j]=cnt[val]+1;
                pre[j]=val;
                info[j]="Take Line#"+to_string(line[i])+" from "+format(val)+" to "+format(j)+ ".";
                heap.push({dist[j], j});
            }else if(dist[j]==dist[val]+w[i]){
                if(cnt[j]>cnt[val]+1){
                    cnt[j]=cnt[val]+1;
                    pre[j]=val;
                    info[j]="Take Line#"+to_string(line[i])+" from "+format(val)+" to "+format(j)+ ".";
                
                }
            }
        }
    }
    vector path;
    cout<>n;
    memset(h, -1, sizeof h);
	rep(i, 1, n+1){
	   // m=rd();
	    cin>>m;
	    rep(j, 0, m){
	       // stop[i]=rd();
	       cin>>stop[j];
	    }
	    rep(j, 0, m){
	        rep(k, 0, j){
	            int len;
	            // 非环路 长度j-k
	            if(stop[0]!=stop[m-1]){
	                len=j-k;
	            }else{ // 环路 长度为j-k，m-1-j+k最小值
	                len=min(j-k, m-1-j+k);
	            }
	            add(stop[j], stop[k], len, i);
	            add(stop[k], stop[j], len, i);
	        }    
	    }
	}
// 	int k=rd();
    int k;
    cin>>k;
	while(k--){
	   // int S=rd(), T=rd();
	    int S, T;
	    cin>>S>>T;
	    dij(S, T);
	}
	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
112
113
114
115
116
117
118
119
120
121
122

参考文献

AcWing 1624. 地铁地图（PAT甲级辅导课）y总视频讲解

原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈