-
Notifications
You must be signed in to change notification settings - Fork 17
/
dijkstra.cpp
77 lines (65 loc) · 1.33 KB
/
dijkstra.cpp
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
#include <bits/stdc++.h>
#define int long long
#define f(i, a, n) for (int i = a; i < n; i++)
#define f1(i,a,n) for(int i=a;i>=n;i--)
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define fastio ios_base::sync_with_stdio(false), cin.tie(NULL);
#define w1 solve();
#define mod (int)(1e9 + 7)
#define prq priority_queue
#define gcd __gcd
#define sz(x) (int)x.size()
#define w(t) int t; cin>>t; while (t--) { solve(); }
#define N 100005
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpi;
const int INF = (int)(1e17);
const double PI = 3.141592653589793;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
string path = "URDL";
vpi arr[1000001];
int dis[1000001];
void dijkstra(int src){
for(int&e:dis) e=INF;
prq<pii , vpi , greater<pii>> pq;
pq.push({0,src});
dis[src]=0;
while(!pq.empty())
{
int u = pq.top().ss;
int dis_u = pq.top().ff;
pq.pop();
if(dis[u]!=dis_u) continue;
for(auto e:arr[u])
{
int v=e.ff;
int vd=e.ss;
if(dis[v]>dis[u]+vd)
{
dis[v]=dis[u]+vd;
pq.push({dis[v],v});
}
}
}
}
void solve()
{
}
int32_t main()
{
fastio
// #ifdef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
w(t)
return 0;
}