dijskra最短路径模板（结合优先队列）

struct node{ int from,to; int time; node(int a, int b, int c): from(a),to(b),time(c){ } }; int N,M,SP,CMAX; vector<node> edge[501]; int dist[501] = {0},bike[501]; int path[501]; bool visited[501] = {false}; struct comp { bool operator() (const pair<int,int> &a,const pair<int,int> &b) const{ if(a.first>b.first) return true; return false; } }; void dij(){ priority_queue<pair<int,int>, vector<pair<int,int> >, comp> pq; for(int i=1; i<=N; ++i) { dist[i] = MAX; visited[i] = false; } for(auto & v : edge[0]) { dist[v.to] = v.time; pq.push(make_pair(v.time,v.to)); path[v.to] = 0; } visited[0] = true; while(!pq.empty()){ pair<int,int> now = pq.top(); pq.pop(); if(visited[now.second]) continue; visited[now.second] = true; int temp = now.second; for(auto &v : edge[temp]){ if(dist[temp] + v.time < dist[v.to]) { dist[v.to] = dist[temp] + v.time; path[v.to] = temp; pq.push(make_pair(dist[v.to],v.to)); } } } }