2019-06-09 12:04:45 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> using namespace std; #define p pair<int,int> int n; vector<vector<p>> graph; vector<int> dis; int v[10000][10000]; void dijkstra(int s){ priority_queue<p,vector<p>,greater<>> que; dis = vector<int>(n,1e9+7); dis[s]=0; que.push(p(s,0)); while(!que.empty()){ p now = que.top(); que.pop(); int nowv = now.first; if(dis[nowv] < now.second)continue; for(auto next:graph[nowv]){ if(dis[next.first] > dis[nowv]+next.second){ dis[next.first] = dis[nowv]+next.second; que.push(p(next.first,dis[next.first])); } } } } int main(void){ int m; cin >> n >> m; vector<int> ans; for(int i=0;i<m;i++){ int a,b,c,d; cin >> a; if(a==1){ cin >> b >> c >> d; b--;c--; graph[b].push_back(p(c,d)); graph[c].push_back(p(b,d)); }else{ cin >> b >> c; b--;c--; dijkstra(b); ans.push_back(dis[c]); } } }
RECOMMEND