Solution of Light OJ 1019 - Brush (V)

/* Bismillahir Rahmanir Rahim Solution-Using Dijkstra algorithm */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) using namespace std; vector<int>vt[109], cost[109]; int dis[109], n; struct node{ int u, w; node(int a, int b){ u=a, w=b; } bool operator < (const node & p)const{ return p.w<w; } }; void dijkstra(int st){ priority_queue<node>q; fi(0, n)dis[i]=1000001; dis[st]=0; q.push(node(st, 0)); while(!q.empty()){ node top=q.top(); q.pop(); int u=top.u; int sz=vt[u].size(); fi(0, sz-1){ int v=vt[u][i]; if(dis[u]+cost[u][i]<dis[v]){ dis[v]=dis[u]+cost[u][i]; q.push(node(v, dis[v])); } } } } int main(){ int t, cs=1, e, u, v, w; cin>>t; while(t--){ cin>>n>>e; fi(0, e-1){ cin>>u>>v>>w; vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } dijkstra(1); cout<<"Case "<<cs++<<": "; if(dis[n]==1000001)cout<<"Impossible"<<endl; else cout<<dis[n]<<endl; fi(0, n){ vt[i].clear(); cost[i].clear(); } } return 0; }