Submission #891920

#	Time	Username	Problem	Language	Result	Execution time	Memory
891920		goodspeed0208	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	219 ms	18372 KiB

commuter_pass

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<utility>
#define int long long
#define INF 1000000000000000000
#define pii pair<long long, long long>
using namespace std;

struct DS{
	int a, b, c;
};

signed main() {
	int n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	vector<vector<pii> >G(n+1);
	int a, b, c;
	while (m--) {
		cin >> a >> b >> c;
		G[a].push_back({b, c});
		G[b].push_back({a, c});
	}
	vector<int>sdis(n+5, INF), tdis(n+5, INF), vdis(n+5, INF);
	sdis[s] = 0;
	set<pii>q; q.insert({0, s});
	//priority_queue<pii, vector<pii>, greater<pii> >q; q.push({0, s});
	while (!q.empty()) {
		auto t = *q.begin(); q.erase(q.begin());
		int len = t.first, i = t.second;
		//cout << i << " " << len << "\n";
		if (len > sdis[i]) continue;
		
		for (auto &j : G[i]) {
			if (sdis[j.first] < len + j.second) continue;
			if (sdis[j.first] != INF) {
				q.erase({sdis[j.first], j.first});
			}
			sdis[j.first] = len + j.second;
			q.insert({sdis[j.first], j.first});
		}
	}
	cout << sdis[1] << "\n";
	//for (int i = 1 ; i <= n ; i++) cout << sdis[i] << " ";
}

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