| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 714588 | Melika0gh | Toll (BOI17_toll) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef long double ld;#define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)#define pb push_back#define mp make_pair#define fi first#define se secondconst int maxn = 5e4 + 10, inf = 1e9 + 7, maxsq = 400, maxlg = 21;//const int mood2 = 97277821, mood3 = 34098487, base = 31;vector<pair<int, int> > adj[maxn], q[maxn];vector<int> vec;int dp[maxn], id[maxn], res[maxn];int k, n, m, o;int main(){ cin >> k >> n >> m >> o; for(int i = 0; i < m; i++) { int v, u, w; cin >> v >> u >> w; adj[v].pb(mp(u, w)); } for(int i = 0; i < o; i++) { int v, u; cin >> v >> u; q[u].pb(mp(v, i)); vec.pb(u); } sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end());
for(int i = 0; i < vec.size(); i++)
id[vec[i]] = i;
for(auto x : vec)
{
fill(dp, dp+n, inf);
int xx = id[x];
dp[x] = 0;
for(int i = x-1; i >= 0; i--)
{
for(auto e : adj[i])
{
int u = e.fi, w = e.se;
if(dp[u] >= inf)
continue;
dp[i] = min(dp[i], dp[u] + w);
}
}
for(auto y : q[x])
res[y.se] = dp[y.fi];
}
for(int i = 0; i < o; i++)
{
if(res[i] >= inf)
cout << -1 << '\n';
else
cout << res[i] << '\n';
}
}