제출 #162987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
162987		Minnakhmetov	Toll (BOI17_toll)	C++14	56 / 100	3047 ms	30044 KiB

toll

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

struct E {
	int a, b, w;
};

const int N = 1e6 + 5, INF = 1e9;
E e[N];
int d[N], ans[N];
vector<pair<int, int>> v[N];
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n, m, k, o;
    cin >> k >> n >> m >> o;

    for (int i = 0; i < m; i++) {
    	cin >> e[i].a >> e[i].b >> e[i].w;
    }

    sort(e, e + m, [](E x, E y) {
    	return x.a < y.a;
    });

    for (int i = 0; i < o; i++) {
    	int x, y;
    	cin >> x >> y;
    	v[x].push_back({y, i});
    }

    for (int i = 0; i < n; i++) {
    	if (!v[i].empty()) {
    		fill(d, d + n, INF);

	    	d[i] = 0;

	    	for (int j = 0; j < m; j++) {
	    		d[e[j].b] = min(d[e[j].b], d[e[j].a] + e[j].w);
	    	}

	    	for (auto p : v[i]) {
	    		if (d[p.first] == INF)
	    			ans[p.second] = -1;
	    		else
	    			ans[p.second] = d[p.first];
	    	}
    	}
    }

    for (int i = 0; i < o; i++) {
    	cout << ans[i] << "\n";
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 0 / 44