Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- long long int dis[100000],d,aaa;
- struct point
- {
- long long int name,val,road;
- bool operator<(const point &a)const
- {
- return a.val<val;
- }
- };
- struct node
- {
- long long int mm,nn,oo;
- };
- vector<node>mp[100000];
- vector<node>::iterator u;
- void dijkstra(point dublin)
- {
- priority_queue<point>pq;
- pq.push(dublin);
- while(!pq.empty())
- {
- point temp;
- temp=pq.top();
- pq.pop();
- if(temp.name==(aaa-1))
- {
- break;
- }
- long long int aa,b,c,x,z,y;
- node r;
- aa=temp.name;
- b=temp.val;
- c=temp.road;
- for(u=mp[aa].begin(); u!=mp[aa].end(); u++)
- {
- r=*u;
- x=r.mm;
- y=r.nn;
- z=r.oo;
- if(c+z<=d)
- {
- point zenit;
- zenit.name=x;
- zenit.val=b+y;
- zenit.road=c+z;
- dis[x]=min(dis[x],b+y);
- pq.push(zenit);
- }
- }
- }
- }
- int main ()
- {
- //freopen("in.txt","w",stdout);
- ios_base::sync_with_stdio(0);
- long long int n,i,b,c,j,x,y,z;
- cin>>n;
- for(i=1; i<=n; i++)
- {
- cin>>aaa>>b>>c>>d;
- for(j=1; j<=b; j++)
- {
- cin>>x>>y>>z;
- node tata;
- tata.mm=y;
- tata.nn=z;
- tata.oo=0;
- mp[x].push_back(tata);
- }
- for(j=1; j<=c; j++)
- {
- cin>>x>>y>>z;
- node tata;
- tata.mm=y;
- tata.nn=z;
- tata.oo=1;
- mp[x].push_back(tata);
- }
- for(j=1; j<aaa; j++)
- {
- dis[j]=1e17;
- }
- point get;
- get.name=0;
- get.val=0;
- get.road=0;
- dijkstra(get);
- if(dis[aaa-1]==1e17)
- {
- cout<<"Case "<<i<<": ";
- cout<<"Impossible"<<endl;
- }
- else
- {
- cout<<"Case "<<i<<": ";
- cout<<dis[aaa-1]<<endl;
- }
- for(j=0; j<aaa; j++)
- {
- mp[j].clear();
- }
- memset(dis,0,sizeof(dis));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement