Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.6 kB
1
Indexable
Never
/*
     বিসমিল্লাহ্
*/

#include <bits/stdc++.h>

using namespace std;
#define FastIO         ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define mp             make_pair
#define si             set <int>
#define vi             vector <int>
// #define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define nl             "\n"
#define INF         1000000000
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
	int x = 1;
	while (b)
	{
		if (b & 1) x *= a;
		a *= a;
		b >>= 1;
	}
	return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr (names + 1, ',');
	cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

//const int N = 200005;






//------------------------Start Here-----------------------//

int cnt = 1;
vector< pair< int , int > > adj [20020]; // adj[u].push_back({v,cost}) ..( u ---cost---> v )
vector< int > d ( 20010, INF );;
vector< int > parent (20010);

void Dijkstra( int start , int n)
{
    d.assign( n, INF);
    parent.assign( n, -1);

    d[start] = 0;
    using pii = pair< int , int >;
    priority_queue< pii , vector<pii> , greater<pii> > q;
    q.push({ d[start] , start });

    while( !q.empty() )
    {
        int d_from = q.top().first;
        int from = q.top().second;
        q.pop();
        if( d_from != d[from] )
        {
            continue;
        }

        for( auto edge : adj[from] )
        {
            int to = edge.first;
            int cost = edge.second;

            if( d[from]+cost < d[to] )
            {
                d[to] = d[from]+cost;
                parent[to] = from;
                q.push({d[to],to});
            }
        }
    }

}

void solve() {
	int n,m,S,T;
	cin>>n>>m>>S>>T;

	for( int i = 0 ; i < m ; i++ )
	{
		int x,y,w;
		cin>>x>>y>>w;
		adj[x].push_back({y,w});
	}

	Dijkstra(S,n);


	if( m == 0 )
	{
		cout<<"Case #"<<cnt<<": "<<"unreachable"<<nl;
		cnt++;
	}
	else
	{
		if( d[T] == INF )
		{
			cout<<"Case #"<<cnt<<": "<<"unreachable"<<nl;
			cnt++;
		}
		else
		{
			cout<<"Case #"<<d[T]<<": "<<"unreachable"<<nl;
			cnt++;
		}
	}


}


//------------------------Main-----------------------//
int32_t main()
{
	FastIO;
/*#ifndef ONLINE_JUDGE
	freopen("input.txt",  "r",  stdin);
	freopen("output.txt", "w", stdout);
#endif*/

	//clock_t z = clock();


	int t = 1;
	cin >> t;
	while (t--) solve();


	//cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);
	
	return 0;
}