Submission #333183

#	Time	Username	Problem	Language	Result	Execution time	Memory
333183		limabeans	Toll (BOI17_toll)	C++17	8 / 100	2381 ms	524292 KiB

toll

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;
const ll inf = 1e18;

struct dsu0 {
    vector<int> par, siz;
    int n;
    int cc;
    int largest;
    void init(int n) {
	assert(n>0);
	this->n=n;
	cc=n;
	par.resize(n+10);siz.resize(n+10);
	for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
	largest=1;
    }
    int parent(int x) {
	assert(x>=0 && x<n);
	return par[x]==x?x:par[x]=parent(par[x]);
    }
    bool join(int x, int y) {
	x=parent(x);y=parent(y);
	if (x==y) return false;
	cc--;
	if (siz[x]<siz[y]) swap(x,y);
	siz[x]+=siz[y];par[y]=x;
	largest=max(largest,siz[x]);
	return true;
    }
};

const int maxn = 5e4+10;

int k,n,m,o;
vector<pair<ll,int>> g[maxn];




map<int,ll> dp[maxn];

ll f(int u, int v) {
    if (u==v) return 0;
    
    if (dp[u].count(v)) return dp[u][v];
    ll res = inf;
    for (auto ed: g[u]) {
	res = min(res, ed.first+f(ed.second,v));
    }

    return dp[u][v] = res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>k>>n>>m>>o;



    for (int i=0; i<m; i++) {
	int u,v; cin>>u>>v;
	int w; cin>>w;
	g[u].push_back({w,v});
    }




    while (o--) {
	int u,v;
	cin>>u>>v;
	ll res = f(u,v);
	if (res>inf/2) res=-1;
	cout<<res<<"\n";
    }
    
    
    return 0;
}

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