Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<pair<int,int> > G[100500];
- vector<int> exits;
- int n, m, k;
- int dijkstra(int at)
- {
- priority_queue<pair<int,int> > pq;
- pq.push(make_pair(0,at));
- vector<int> dist;
- dist.resize(n);
- for(int i=0;i<n;i++)
- dist[i] = 1e9;
- bool vis[n][2];
- memset(vis,false,sizeof(vis));
- for(int i=0;i<exits.size();i++)
- vis[exits[i]][0] = true;
- dist[0] = 0;
- while(!pq.empty())
- {
- pair<int,int> state = pq.top();
- pq.pop();
- int city = state.second;
- int path = -state.first;
- if(city == 0 && vis[city][0] == true)
- break;
- if(vis[city][0] == false)
- {
- cout<<city<<" "<<path<<endl;
- vis[city][0] = true;
- vector<pair<int,int> > can_go = G[city];
- for(int i=0;i<can_go.size();i++)
- {
- int next = can_go[i].first;
- int dist_between = can_go[i].second;
- if(dist[next] > dist[city] + dist_between && vis[next][0] == false)
- {
- dist[next] = dist[city] + dist_between;
- pq.push(make_pair(-dist[next], next));
- }
- else if(vis[next][0] == true)
- dist[next] = dist[city] + dist_between;
- }
- }
- if(vis[city][1] == false)
- continue;
- }
- int naj = -1;
- int sec_naj = -1;
- for(int i=0;i<exits.size();i++)
- {
- if(dist[exits[i]] >= naj)
- {
- sec_naj = naj;
- naj = dist[exits[i]];
- }
- }
- return sec_naj;
- }
- int main()
- {
- cin>>n>>m>>k;
- for(int i=0;i<m;i++)
- {
- int from, to, weigh;
- cin>>from>>to>>weigh;
- G[from].push_back(make_pair(to,weigh));
- G[to].push_back(make_pair(from,weigh));
- }
- for(int i=0;i<k;i++)
- {
- int a;
- cin>>a;
- exits.push_back(a);
- }
- cout<<dijkstra(0)<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement