Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- using namespace std;
- #define MAX_N 30000
- #define INFINITY 1000000000
- int n,m,s,t,numtest;
- vector<int> adj[MAX_N];
- vector<int> weight[MAX_N];
- void read_input()
- {
- cin >> n >> m >> s >> t;
- for(int i=0; i<n; i++) {
- adj[i].clear();
- weight[i].clear();
- }
- for(int i=0; i<m; i++) {
- int u,v,w;
- cin >> u >> v >> w;
- adj[u].push_back(v);
- weight[u].push_back(w);
- adj[v].push_back(u);
- weight[v].push_back(w);
- }
- }
- int d[MAX_N];
- bool scanned[MAX_N];
- set<pair<int,int>> Q;
- void shortest_path(int s, int t)
- {
- Q.clear();
- for(int i=0; i<n; i++) {
- d[i] = INFINITY;
- scanned[i] = false;
- Q.insert(make_pair(d[i],i));
- }
- d[s] = 0;
- Q.insert(make_pair(0,s));
- while(true) {
- int mind = INFINITY + 1;
- int u = -1;
- /*
- for(int v=0; v<n; v++)
- if((!scanned[v]) && (d[v] < mind)) {
- u = v;
- mind = d[v];
- }
- */
- pair<int,int> smallest = *(Q.begin());
- Q.erase(Q.begin());
- u = smallest.second;
- mind = d[u];
- if(scanned[u])
- continue;
- if(mind >= INFINITY) {
- break;
- }
- if(u==t) {
- cout << d[u] << endl;
- return;
- }
- scanned[u] = true;
- for(int i=0; i<adj[u].size(); i++) {
- int v = adj[u][i];
- int w = weight[u][i];
- if(d[u] + w < d[v]) {
- d[v] = d[u] + w;
- Q.insert(make_pair(d[v],v));
- }
- }
- }
- cout << "unreachable\n";
- }
- main()
- {
- cin >> numtest;
- for(int i=0; i<numtest; i++) {
- read_input();
- cout << "Case #" << (i+1) << ": ";
- shortest_path(s,t);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement