Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define INF 1e7
- vector< pair<int,int> >edges[101];
- int dis[101],n;
- void dijkstra()
- {
- int i;
- for(i=1;i<=n;i++)
- dis[i]=INF;
- dis[1]=0;
- priority_queue < pair<int,int> , vector< pair<int,int> > , greater < pair<int,int> > > pq;
- pq.push(make_pair(dis[1],1));
- while(!pq.empty())
- {
- int u = pq.top().second;
- pq.pop();
- for(int i=0;i<edges[u].size();i++)
- {
- int v = edges[u][i].first;
- int w = edges[u][i].second;
- if(dis[v]>dis[u]+w)
- {
- dis[v]=dis[u]+w;
- pq.push(make_pair(dis[v],v));
- }
- }
- }
- return;
- }
- int main()
- {
- int t,i,j,k,l,m,u,v,w;
- scanf("%d",&t);
- for(i=1;i<=t;i++)
- {
- scanf("%d%d",&n,&m);
- for(j=1;j<=n;j++)
- edges[j].clear();
- for(j=0;j<m;j++)
- {
- scanf("%d%d%d",&u,&v,&w);
- edges[u].push_back(make_pair(v,w));
- edges[v].push_back(make_pair(u,w));
- }
- dijkstra();
- if(dis[n]==INF)
- printf("Case %d: Impossible\n",i);
- else
- printf("Case %d: %d\n",i,dis[n]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement