Submission #1028469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028469		snpmrnhlol	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	39 ms	4184 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
const int N = 200;
const int inf = 1e9;
vector<vector<array<int,4>>> e;
vector<vector<array<int,4>>> r;
///find best two paths from
pair<int,int>b[N];
vector <int> dist0;
vector <int> distn;
vector <int> dist02;
vector <int> distn2;
vector <int> disttmp;
priority_queue <pair<int,int>> pq;
int n,m;
void dj(int node,vector<vector<array<int,4>>> &e,vector <int> &dist){
    dist.resize(n);
    for(int i = 0;i < n;i++){
        dist[i] = inf;
        b[i] = {-1,-1};
    }
    dist[node] = 0;
    b[node] = {-1,-1};
    pq.push({-dist[node],node});
    while(!pq.empty()){
        int d = -pq.top().first;
        int id = pq.top().second;
        pq.pop();
        if(d > dist[id])continue;
        for(int i = 0;i < e[id].size();i++){
            array<int,4> edge = e[id][i];
            if(dist[edge[0]] > d + edge[1]){
                b[edge[0]] = {id,edge[1]};
                dist[edge[0]] = d + edge[1];
                pq.push({-dist[edge[0]],edge[0]});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    e.resize(n);
    r.resize(n);
    for(int i = 0;i < m;i++){
        int u,w,c,d;
        cin>>u>>w>>c>>d;
        u--;w--;
        e[u].push_back({w,c,d,0});
        r[w].push_back({u,c,d,0});
    }
    int cur;
    dj(0,e,dist0);cur = n - 1;
    while(1){
        pair<int,int> nr = b[cur];
        if(nr.first == -1)break;
        for(auto &i:e[nr.first]){
            if(i[0] == cur && i[1] == nr.second){
                i[3] = 1;
            }
        }
        cur = nr.first;
    }
    dj(n - 1,e,distn);cur = 0;
    while(1){
        pair<int,int> nr = b[cur];
        if(nr.first == -1)break;
        for(auto &i:e[nr.first]){
            if(i[0] == cur && i[1] == nr.second){
                i[3] = 1;
            }
        }
        cur = nr.first;
    }
    dj(0,r,dist02);
    dj(n - 1,r,distn2);
    int ans = inf;
    ans = min(ans,distn[0] + dist0[n - 1]);
    for(int i = 0;i < n;i++){
        for(int _ = 0;_ < e[i].size();_++){
            array <int,4> j = e[i][_];
            if(j[3] == 1){
                ///brute force
                int cur = j[2];
                swap(e[i][_],e[i].back());
                e[i].pop_back();
                e[j[0]].push_back({i,j[1],j[2],0});
                dj(0,e,disttmp);
                cur+=disttmp[n - 1];
                cur = min(cur,inf);
                dj(n - 1,e,disttmp);
                cur+=disttmp[0];
                cur = min(cur,inf);
                ans = min(ans,cur);
                e[j[0]].pop_back();
                e[i].push_back(j);
                swap(e[i][_],e[i].back());
            }else{
                ///luck time
                ans = min(ans,j[2] + min(j[1] + dist0[j[0]] + distn2[i],dist0[n - 1]) + min(j[1] + distn[j[0]] + dist02[i],distn[0]));
            }
        }
    }
    if(ans == inf)ans = -1;
    cout<<ans<<'\n';
    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'void dj(int, std::vector<std::vector<std::array<int, 4> > >&, std::vector<int>&)':
ho_t4.cpp:30:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int i = 0;i < e[id].size();i++){
      |                       ~~^~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:79:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int _ = 0;_ < e[i].size();_++){
      |                       ~~^~~~~~~~~~~~~

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