Submission #1039189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039189		n3rm1n	Toll (BOI17_toll)	C++17	18 / 100	3055 ms	10836 KiB

toll

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 5e4 + 10, MAXM = 1e4 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long k, n, m, q;
vector < pair < long long, long long > > g[MAXN];
void read()
{
    cin >> k >> n >> m >> q;
    for (long long i = 1; i <= m; ++ i)
    {
        long long x, y, c;
        cin >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
    }
}

long long isstart[MAXN];
vector < pair < long long, long long > > que[MAXN];
long long st, dist[MAXN], inf = 1e17; /// fix
long long visited[MAXN];
void dijkstra()
{
    for (long long i = 0; i < n; ++ i)
    {
        dist[i] = inf;
        visited[i] = 0;
    }
    dist[st] = 0;

    priority_queue < pair < long long, long long > > q;
    q.push({0, st});

    long long wver, wdist;
    while(q.size())
    {
        wdist = -q.top().first;
        wver = q.top().second;
        q.pop();
        if(visited[wver])continue;
        visited[wver] = 1;
        for (auto nb: g[wver])
        {
            if(dist[nb.first] > dist[wver] + nb.second)
            {
                dist[nb.first] = dist[wver] + nb.second;
                q.push(make_pair(-dist[nb.first], nb.first));
            }
        }
    }


}
long long ans[MAXN];
void precompute()
{
    for (long long i = 1; i <= q; ++ i)
    {
        long long from, to;
        cin >> from >> to;
        que[from].push_back({to, i});
        isstart[from] = 1;
    }

    memset(ans, -1, sizeof(ans));
    for (long long i = 0; i < n; ++ i)
    {
        if(!isstart[i])continue;
       // cout << i << endl;

        st = i;
        dijkstra();

        for (auto to: que[i])
        {
           // cout << "to " << to.first << " " << dist[to.first] << endl;
            if(dist[to.first] != inf)ans[to.second] = dist[to.first];
        }
    }
    for (long long i = 1; i <= q; ++ i)
        cout << ans[i] << endl;
}
int main()
{
    speed();

    read();
    precompute();
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'void dijkstra()':
toll.cpp:40:21: warning: variable 'wdist' set but not used [-Wunused-but-set-variable]
   40 |     long long wver, wdist;
      |                     ^~~~~

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