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
| namespace Dijkstra{
#define pp pair<int,int>
#define f first
#define s second
const int MAXN = 1e5+5;
const int MAXM = 2e5+5;
int n,m,k,dist[MAXN],head[MAXN],tot;
struct Edge{
int f,t,nxt,dis;
}edge[MAXM];
inline void add(int f,int t, int d){
edge[++tot].f = f;
edge[tot].t = t;
edge[tot].dis = d;
edge[tot].nxt = head[f];
head[f] = tot;
}
inline void dij(int source){
priority_queue<pp> q;
memset(dist,0x3f3f,sizeof(dist));
dist[source] = 0;
q.push(make_pair(0,source));
while(!q.empty()){
int qf = -q.top().f,qs = q.top().s; q.pop();
if (dist[qs]<qf) continue;
for (int i=head[qs];i;i=edge[i].nxt){
int v = edge[i].t,d = edge[i].dis;
if (dist[v]>dist[qs]+d){
dist[v] = dist[qs]+d;
q.push(make_pair(-dist[v],v));
}
}
}
}
inline int dijk(int source, int to){
priority_queue<pp> q;
memset(dist,0x3f3f,sizeof(dist));
dist[source] = 0;
q.push(make_pair(0,source));
while(!q.empty()){
int qf = -q.top().f,qs = q.top().s; q.pop();
if (dist[qs]<qf) continue;
if (qs==to) return dist[to];
for (int i=head[qs];i;i=edge[i].nxt){
int v = edge[i].t,d = edge[i].dis;
if (dist[v]>dist[qs]+d){
dist[v] = dist[qs]+d;
q.push(make_pair(-dist[v],v));
}
}
}
return 0x3f3f;
}
void init();
void solve();
}
|
