Last active
August 29, 2015 14:00
-
-
Save yipo/c584c4902503af3097d7 to your computer and use it in GitHub Desktop.
The Tourist Guide
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <vector> | |
#include <queue> | |
#include <iostream> | |
using namespace std; | |
typedef int vertex; | |
typedef vector< pair<vertex,int> > edge_list; | |
const int MAX=1<<30; | |
class graph { | |
vector<edge_list> edge; | |
public: | |
graph(int size) : edge(1+size) {} | |
void add_edge(vertex u,vertex v,int w) { | |
edge[u].push_back(make_pair(v,w)); | |
edge[v].push_back(make_pair(u,w)); | |
} | |
const edge_list &get_edge(vertex u) const { | |
return edge[u]; | |
} | |
}; | |
struct candidate_vertex { | |
vertex key; | |
int value; | |
candidate_vertex(vertex v,int bound) : key(v),value(bound) {} | |
bool operator <(const candidate_vertex &obj) const { | |
return value<obj.value; | |
} | |
}; | |
int bound_dijkstra(int n,const graph &g,int s,int d) { | |
vector<bool> pass(1+n); | |
vector<int> bound(1+n); | |
priority_queue<candidate_vertex> heap; | |
heap.push(candidate_vertex(s,bound[s]=MAX)); | |
while (heap.size()>0) { | |
vertex u=heap.top().key; | |
if (u==d) break; | |
heap.pop(); | |
if (pass[u]) continue; | |
pass[u]=true; | |
const edge_list &list=g.get_edge(u); | |
for (int i=0;i<list.size();i++) { | |
vertex v=list[i].first; | |
if (pass[v]) continue; | |
int alt=min(bound[u],list[i].second); | |
bound[v]=max(bound[v],alt); | |
heap.push(candidate_vertex(v,bound[v])); | |
} | |
} | |
return bound[d]; | |
} | |
int minimum_trips(int n,const graph &g,int s,int d,int t) { | |
int capacity=bound_dijkstra(n,g,s,d)-1; | |
return t/capacity + (t%capacity>0? 1: 0); | |
} | |
int main() { | |
int k=1,n,r; | |
while (cin>>n>>r) { | |
if (n==0&&r==0) break; | |
graph g(n); | |
for (int i=0;i<r;i++) { | |
int c1,c2,p; | |
cin>>c1>>c2>>p; | |
g.add_edge(c1,c2,p); | |
} | |
int s,d,t; | |
cin>>s>>d>>t; | |
cout<<"Scenario #"<<k++<<endl; | |
cout<<"Minimum Number of Trips = "<<minimum_trips(n,g,s,d,t)<<endl; | |
cout<<endl; | |
} | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment