Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cstdio>
- #include<vector>
- #include<queue>
- #include<algorithm>
- #include<cstring>
- #include<utility>
- using namespace std;
- #define mx 100002
- #define w first
- #define u second
- #define pb push_back
- #define mp make_pair
- typedef pair <int, int> pii;
- vector<int>graph[mx],cost[mx];
- long long dist[mx];
- int parent[mx];
- void dijkstra(int n)
- {
- for(int i=0;i<=n;i++)
- parent[i]=dist[i]=-1;
- priority_queue<pii,vector<pii > ,greater<pii > >Q;
- Q.push(mp(0,1));
- dist[1]=0;
- while(!Q.empty())
- {
- pii top=Q.top();
- Q.pop();
- int u=top.u;
- for(int i=0; i<(int)graph[u].size(); i++)
- {
- int v=graph[u][i];
- if(dist[u]+cost[u][i]<dist[v]||dist[v]==-1)
- {
- dist[v]=dist[u]+cost[u][i];
- parent[v]=u;
- Q.push(mp(dist[v],v));
- }
- }
- }
- }
- int main()
- {
- int n,e;
- scanf("%d%d",&n,&e);
- for(int i=0; i<e; i++)
- {
- int u,v,w;
- scanf("%d %d %d",&u,&v,&w);
- graph[u].push_back(v);
- graph[v].push_back(u);
- cost[u].push_back(w);
- cost[v].push_back(w);
- }
- dijkstra(n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment