Submission #700889

#	Time	Username	Problem	Language	Result	Execution time	Memory
700889		Ran	Commuter Pass (JOI18_commuter_pass)	C++17	55 / 100	325 ms	34380 KiB

commuter_pass

#include <bits/stdc++.h>

#define fi first
#define se second
#define ll long long

using namespace std;

const int N = 1e5 + 100;

ll n, m, S, T, U, V;

ll dis[N][3];

bool dd[N][2];

vector < pair <ll, ll> > adj[N];

void Dijkstra(int type, int batdau)
{
    for (int i = 1; i <= n; i++)
        dis[i][type] = 1e18;
    dis[batdau][type] = 0;
    priority_queue < pair<ll, ll> > inside;
    inside.push({-dis[batdau][type], batdau});
    while (inside.size() != 0)
    {
        pair <ll, ll> cur = inside.top(); inside.pop();
        int u = cur.se;
        ll kk = -cur.fi;
        if (dis[u][type] < kk)
            continue;
        for (int i = 0; i < adj[u].size(); i++)
        {
            pair <ll, ll> tmp = adj[u][i];
            int v = tmp.fi;
            ll val = tmp.se;
            if (kk + val < dis[v][type])
            {
                dis[v][type] = kk + val;
                inside.push({-dis[v][type], v});
            }
        }
    }
}

void dfs(int u, int type)
{
    dd[u][type] = true;
    for (int i = 0; i < adj[u].size(); i++)
    {
        pair <ll, ll> tmp = adj[u][i];
        int v = tmp.fi;
        long long val = tmp.se;
        if (dis[u][2] - val == dis[v][2] && dd[v][type] == false)
            dfs(v, type);
    }
}

void sub1()
{
    Dijkstra(2, S);
    Dijkstra(1, V);
    dfs(T, 0);
    long long ans = dis[U][1];
    for (int i = 1; i <= n; i++)
        if (dd[i][0] == true)
            ans = min(ans, dis[i][1]);
    cout << ans;
}

void sub3()
{
    Dijkstra(2, S);
    Dijkstra(0, U);
    Dijkstra(1, V);
    dfs(T, 0);
    long long ans = dis[U][1];
    for (int i = 1; i <= n; i++)
        if (dd[i][0] == true)
        {
            for (int j = 1; j <= n; j++)
                dd[j][1] = false;
            dfs(i, 1);
            for (int j = 1; j <= n; j++)
                if (dd[j][1] == true)
                {
                    ans = min(ans, dis[i][0] + dis[j][1]);
                    ans = min(ans, dis[i][1] + dis[j][0]);
                }
        }
    cout << ans;
}

set < pair<ll, ll> > xoa;

void dfs2(int u, int type)
{
    dd[u][type] = true;
    for (int i = 0; i < adj[u].size(); i++)
    {
        pair <ll, ll> tmp = adj[u][i];
        int v = tmp.fi;
        long long val = tmp.se;
        if (dis[u][2] - val == dis[v][2] && dd[v][type] == false)
        {
            dfs2(v, type);
            adj[u][i] = {v, 0};
            xoa.insert({v, u});
        }
    }
}

void sub2()
{
    Dijkstra(2, S);
    dfs2(T, 0);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < adj[i].size(); j++)
        {
            pair<ll, ll> tmp = adj[i][j];
            if (xoa.find({i, tmp.fi}) != xoa.end())
                adj[i][j] = {tmp.fi, 0};
        }
    }
    Dijkstra(0, U);
    long long ans = dis[V][0];
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    cin >> S >> T;
    cin >> U >> V;
    for (int i = 1; i <= m; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    if (S == U)
        sub1();
    else
        if (n <= 300)
            sub3();
        else
            sub2();
    return 0;
};

Compilation message (stderr)

commuter_pass.cpp: In function 'void Dijkstra(int, int)':
commuter_pass.cpp:33:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int i = 0; i < adj[u].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(int, int)':
commuter_pass.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < adj[u].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs2(int, int)':
commuter_pass.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i = 0; i < adj[u].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void sub2()':
commuter_pass.cpp:120:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for (int j = 0; j < adj[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~

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