priority_queue优化Dijkstra最短路径算法

 1 #include <bits/stdc++.h>
 2 #define fi first
 3 #define se second
 4 #define pb push_back
 5 #define fio ios::sync_with_stdio(false);cin.tie(0);
 6 #define pii pair<int,int>
 7 #define vi vector<int>
 8 #define vc vector<char>
 9 #define mii map<int,int>
10 #define si(a) scanf("%d",&a)
11 #define ss(a) scanf("%s",&a)
12 #define sl(a) scanf("%I64d",&a);
13 #define slf(a) scanf("%lf",&a);
14 #define CLEAR(a,b) memset(a,b,sizeof(a))
15 #define pi acos(-1)
16 typedef long long ll;
17 typedef unsigned long long ull;
18 typedef double db;
19 const int INF=0x3f3f3f3f;
20 const int N=2e5+5;
21 using namespace std;
22 
23 priority_queue< int,vector<int>,greater<int> > pqg;
24 priority_queue< int,vector<int>,less<int> > pql;
25 
26 
27 struct edge
28 {
29     int to,cost;
30 };
31 //first是最短距离，second是顶点的编号
32 int v;//顶点个数
33 vector<edge> G[N];
34 int dis[N];
35 priority_queue<pii,vector<pii>,greater<pii> > que;
36 
37 void dijkstra(int start)
38 {
39     memset(dis,INF,sizeof dis);
40     dis[start] = 0;
41     que.push(make_pair(0,start)); //把起点推入队列
42     while(!que.empty())
43     {
44         pii p = que.top(); que.pop();
45         int v = p.second; //顶点的编号
46         if (dis[v] < p.first) continue;
47         for(int i = 0; i < G[v].size(); i++)
48         {
49             edge e = G[v][i];
50             if (dis[e.to] > dis[v] + e.cost)
51             {
52                 dis[e.to] = dis[v] + e.cost;
53                 que.push(make_pair(dis[e.to],e.to));
54             }
55         }
56     }
57 }
58 
59 int main()
60 {
61     
62 }