Submission #233677

#	Time	Username	Problem	Language	Result	Execution time	Memory
233677		Charis02	Commuter Pass (JOI18_commuter_pass)	C++14	24 / 100	87 ms	4480 KiB

commuter_pass

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 304
#define INF 1e18

using namespace std;

ll n,m,s,t,u,v;
ll d[N][N];
vector < pi > graph[N];

void dijkstra(int root,int id)
{
    rep(i,0,n+1)
    {
        d[i][id] = INF;
    }

    priority_queue < pi > pq;
    pq.push(mp(0,root));
    d[root][id] = 0;

    while(!pq.empty())
    {
        pi cur = pq.top();
        pq.pop();
        cur.first*=-1;

        if(d[cur.second][id] < cur.first)
            continue;

        rep(i,0,graph[cur.second].size())
        {
            ll vv = graph[cur.second][i].first;
            ll cc = graph[cur.second][i].second;

            if(d[vv][id] > cur.first+cc)
            {
                d[vv][id]=cur.first+cc;
                pq.push(mp(-d[vv][id],vv));
            }
        }
    }

    return;
}

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

    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;

    rep(i,0,m)
    {
        ll a,b,c;
        cin >> a >> b >> c;
        graph[a].push_back(mp(b,c));
        graph[b].push_back(mp(a,c));
    }

    if(n > 300)
        return 0;

    rep(i,1,n+1)
    {
        dijkstra(i,i);
    }

    ll ans = d[u][v];

    rep(x,1,n+1)
    {
        rep(y,1,n+1)
        {
            if(d[s][x]+d[x][y]+d[y][t]==d[s][t])
            {
                ans = min(ans,d[u][y]+d[v][x]);
                ans = min(ans,d[u][x]+d[v][y]);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, int)':
commuter_pass.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
commuter_pass.cpp:44:13:
         rep(i,0,graph[cur.second].size())
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:44:9: note: in expansion of macro 'rep'
         rep(i,0,graph[cur.second].size())
         ^~~

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