Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream in ("parc.in");
- ofstream out ("parc.out");
- #define INF 1000000000
- #define MAXN 102
- priority_queue <pair <int, int> > q;
- vector <pair <int, int> >g[MAXN+1];
- int dist[MAXN+1];
- int v[MAXN];
- int n;
- void dijkstra(int start) {
- int son, node, cost, dist_son, i;
- for(i=1; i<=n; i++)
- dist[i]=INF;
- dist[start]=0;
- q.push({0, start});
- while(!q.empty()) {
- cost=-q.top().first;
- node=q.top().second;
- q.pop();
- if(cost<=dist[node])
- for(i=0; i<g[node].size(); i++) {
- dist_son=-g[node][i].first;
- son=g[node][i].second;
- if(dist[son]>dist_son+cost) {
- dist[son]=dist_son+cost;
- q.push({-dist[son], son});
- }
- }
- }
- }
- int main()
- {
- int m, a, b, c, cost, p, i, poarta, minim;
- in>>n>>m>>c;
- for(i=0; i<m; i++) {
- in>>a>>b>>cost;
- g[a].push_back({-cost, b});
- }
- in>>p;
- for(i=0; i<p; i++)
- in>>v[i];
- dijkstra(c);
- minim=INF;
- for(i=0; i<p; i++) {
- if(dist[v[i]]==INF)
- dist[v[i]]=0;
- if(dist[v[i]]<minim) {
- minim=dist[v[i]];
- poarta=v[i];
- }
- }
- out<<poarta;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement