TOJ 565
題敘
https://toj.tfcis.org/oj/pro/565/
給一張捷運的路線圖以及兩個整數 $A$ $B$ 和起點 $S$，從 $i$ 站到 $j$ 站所需要的花費為
$A經過路線數 + B經過路線權重總和$
求 $S$ 到各點所需的最小花費
想法
Dijkstra 模板題
如果點 $i$ 到點 $j$ 最短路徑為 $A$
則點 $i$ 到 $A$ 上的任一點的路徑也必定為最短路徑 (前提是邊權都是正的)
所以，我們可以每次都走距離最短的路，不斷更新起點到終點的距離，最終更新完必定會是最短距離
Code
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
|
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N = 1e5+10;
const int INF = 9223372036854775807;
int n,m,a,b,s;
vector<pii> E[N];
vector<int> dis(N,INF);
void dijkstra(){
priority_queue<pii> pq;
pq.emplace(dis[s]=0,s);
while(pq.size()){
int d,u;
tie(d,u)=pq.top();
d*=(-1);
pq.pop();
if(d!=dis[u]) continue;
for(auto e: E[u]){
int w,v;
tie(w,v)=e;
if(dis[v]<=dis[u]+a+b*w) continue;
dis[v]=dis[u]+a+b*w;
pq.emplace(-dis[v],v);
}
}
}
signed main(){
cin>>n>>m>>a>>b>>s;
for(int i=0,u,v,w ; i<m ; i++){
cin>>u>>v>>w;
E[u].emplace_back(w,v);
E[v].emplace_back(w,u);
}
dijkstra();
for(int i=1 ; i<=n ; i++){
cout<<dis[i]<<" ";
}
cout<<"\n";
return 0;
}
|
複雜度
使用 priority_queue 維護要加入的邊，複雜度為 $O(logN)$
總共有 $N$ 個點，總複雜度為 $O(NlogN)$