제출 #228354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228354		AaronNaidu	Shortcut (IOI16_shortcut)	C++14	23 / 100	2100 ms	198520 KiB

shortcut

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

vector<pair<int, int> > graph[100000];
ll dist1s[100000];
bool visited[100000];
ll distMatrix[5000][5000];
int n, c;

void DFS(int node) {
    visited[node] = true;
    for (auto i : graph[node])
    {
        if (!visited[i.first])
        {
            dist1s[i.first] = i.second + dist1s[node];
            DFS(i.first);
        }
    }
}

ll bridgeBetween(int fir, int sec) {
    ll toRet = 0;
    for (int i = 0; i < 2 * n; i++)
    {
        for (int j = i + 1; j < 2 * n; j++)
        {
            if (distMatrix[i][j] < 1000000000000000000)
            {
                toRet = max(toRet, min(distMatrix[i][j], min(distMatrix[i][fir] + c + distMatrix[sec][j], distMatrix[i][sec] + c + distMatrix[fir][j])));
            }
            
        }
        
    }
    return toRet;
}

void trash()  {
    //cout << "Starting first DFS\n";
    DFS(0);
    //cout << "Done with first DFS\n";
    ll maxDist = 0;
    int maxVert = -1;
    for (int i = 0; i < 2 * n; i++)
    {
        if (maxDist < dist1s[i])
        {
            maxDist = dist1s[i];
            maxVert = i;
        }
        dist1s[i] = 0;
        visited[i] = false;
    }
    DFS(maxVert);
    ll maxDist2 = 0;
    int maxVert2 = -1;
    for (int i = 0; i < 2 * n; i++)
    {
        if (maxDist2 < dist1s[i])
        {
            maxDist2 = dist1s[i];
            maxVert2 = i;
        }
        dist1s[i] = 0;
    }
    if (maxVert >= n)
    {
        maxVert -= n;
    }
    if (maxVert2 >= n)
    {
        maxVert2 -= n;
    }
    
    graph[maxVert].push_back({maxVert2, c});
    graph[maxVert2].push_back({maxVert, c});
    //cout << "Edge between " << maxVert << " and " << maxVert2 << "\n";
}

ll find_shortcut(int ln, vector<int> l, vector<int> d, int lc) {
    n = ln;
    c = lc;
    //cout << "Starting\n";
    for (int i = 0; i < l.size(); i++)
    {
        graph[i].push_back({i+1, l[i]});
        graph[i+1].push_back({i, l[i]});
    }
    for (int i = 0; i < d.size(); i++)
    {
        if (d[i] > 0)
        {
            graph[i].push_back({i+n, d[i]});
            graph[i+n].push_back({i, d[i]});
        }
    }
    
    priority_queue<pair<ll, ll> > q;
    for (int i = 0; i < 5000; i++)
    {
        for (int j = 0; j < 5000; j++)
        {
            distMatrix[i][j] = 1000000000000000000;
        }
        
    }
    
    for (int i = 0; i < 2 * n; i++)
    {
        q.push({0, i});
        for (int j = 0; j < 2 * n; j++)
        {
            visited[j] = false;
        }
        distMatrix[i][i] = 0;
        while (!q.empty())
        {
            int dist = -q.top().first;
            int node = q.top().second;
            q.pop();
            if (visited[node])
            {
                continue;
            }
            visited[node] = true;
            for (auto j : graph[node])    
            {
                if (!visited[j.first])
                {
                    distMatrix[i][j.first] = min(distMatrix[i][j.first], distMatrix[i][node] + j.second);
                    //cout << "Updating distMatrix " << i << j.first << " to " <<  min(distMatrix[i][j.first], distMatrix[i][node] + j.second) << "\n";
                    q.push({-distMatrix[i][j.first], j.first});
                }
            }
        }
    }
    ll toRet = 1000000000000000000;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (distMatrix[i][j] < 1000000000000000000)
            {
                toRet = min(toRet, bridgeBetween(i,j));
            }
        }
    }
    return toRet;
}

컴파일 시 표준 에러 (stderr) 메시지

shortcut.cpp: In function 'll find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < l.size(); i++)
                     ~~^~~~~~~~~~
shortcut.cpp:91:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < d.size(); i++)
                     ~~^~~~~~~~~~
shortcut.cpp:120:17: warning: unused variable 'dist' [-Wunused-variable]
             int dist = -q.top().first;
                 ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3