Submission #1114826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114826		AdamGS	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1066 ms	262144 KiB

ho_t4

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

struct Edge{
    int other, len, swapCost;
    bool active=true;
};

vector<vector<Edge>> graph;
vector<bool> found;

int Dijkstra(int v1, int v2){
    for (int i=0;i<found.size();i++) found[i]=false;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, v1});
    while (!pq.empty()){
        pair<int, int> p=pq.top();
        pq.pop();
        if (p.second==v2) return p.first;
        found[p.second]=true;
        for (Edge e:graph[p.second]){
            if (e.active&&!found[e.other]) pq.push({p.first+e.len, e.other});
        }
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin>>n>>m;
    graph.resize(n+7);
    found.resize(n+7);
    for (int i=0;i<m;i++){
        Edge e;
        int v;
        cin>>v>>e.other>>e.len>>e.swapCost;
        graph[v].push_back(e);
    }
    int d1=Dijkstra(1, n), d2=Dijkstra(n, 1), out;
    if (d1==-1||d2==-1) out=-1;
    else out=d1+d2;
    for (int i=1;i<=n;i++){
        for (int j=0;j<graph[i].size();j++){
            graph[i][j].active=false;
            Edge e;
            e.len=graph[i][j].len;
            e.other=i;
            graph[graph[i][j].other].push_back(e);
            int dist1=Dijkstra(1, n), dist2=Dijkstra(n, 1), res;
            graph[graph[i][j].other].pop_back();
            graph[i][j].active=true;
            if (dist1==-1||dist2==-1) res=-1;
            else res=dist1+dist2+graph[i][j].swapCost;
            if (out==-1) out=res;
            else  if (res!=-1) out=min(out, res);
        }
    }
    cout<<out<<'\n';
    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int Dijkstra(int, int)':
ho_t4.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i=0;i<found.size();i++) found[i]=false;
      |                  ~^~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int j=0;j<graph[i].size();j++){
      |                      ~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63