Submission #404290

#	Time	Username	Problem	Language	Result	Execution time	Memory
404290		dreezy	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	541 ms	32040 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define pb push_back
#define f first
#define s second

const ll inf = LLONG_MAX;
const int maxn = 1e5 +10;
map<int, int> graph[maxn];


ll dist[maxn];
int inds[maxn];
bool vis[maxn];

void dijkstra(int n, int s){
	for(int i =1; i <=n; i++){
		dist[i] = inf;
	}
	
	memset(vis, 0, sizeof(vis));
	
	using T = pair<ll, int>;
	priority_queue<T, vector<T>, greater<T>> pq;
	
	dist[s] = 0;
	pq.push({0,s});
	
	while(pq.size()){
		int curnode = pq.top().second;
		ll curdist  =pq.top().first;
		pq.pop();
		
		if(vis[curnode]) continue;
		vis[curnode] = true;
		
		for(pi adj : graph[curnode]){
			if(curdist + adj.s < dist[adj.f]){
				dist[adj.f] = curdist + adj.s;
				inds[adj.f] = curnode;
				pq.push({dist[adj.f], adj.f});
			}
		}
	}
}

int main(){
	int n, m, s, t, u, v;
	cin >> n >> m >>s >>t >> u >>v;
	
	for(int i =0; i <m;i++){
		int a, b,c; cin>> a>> b >> c;
		
		graph[a].insert({b,c});
		graph[b].insert({a, c});
	}
	
	dijkstra(n, s);
	
	int cur = t;
	while(cur!= s ){
		graph[cur][inds[cur]] = 0;
		graph[inds[cur]][cur] = 0;
		cur = inds[cur];
	}
	
	dijkstra(n, u);
	
	cout << dist[v]<<endl;

}

• Subtask 1: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45