oj.uz

Submission #747111

# Submission time Handle Problem Language Result Execution time Memory
747111 2023-05-23T16:03:21 Z 1075508020060209tc Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 4948 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;int m;
int uar[50010];int var[50010];int war[50010];int dar[50010];
int dis[210];
int rdis[210];
int vis[210];
int odis[210];
int ordis[210];
vector<pair<int,int>>e[210];
int dijkstera(){
for(int i=1;i<=n;i++){
    dis[i]=1e18;
    vis[i]=0;
    rdis[i]=1e18;
    e[i].clear();
}
for(int i=1;i<=m;i++){
    e[uar[i]].push_back({var[i],war[i]});
}

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
dis[1]=0;
pq.push({0,1});
while(pq.size()){
    int nw=pq.top().second;
    pq.pop();
    if(vis[nw]){continue;}
    vis[nw]=1;
    for(int i=0;i<e[nw].size();i++){
        int v=e[nw][i].first;
        int w=e[nw][i].second;
        if(dis[v]>dis[nw]+w){
            dis[v]=dis[nw]+w;
            pq.push({dis[v],v});
        }
    }
}


rdis[n]=0;
pq.push({0,n});
while(pq.size()){
    int nw=pq.top().second;
    pq.pop();
    if(vis[nw]==2){continue;}
    vis[nw]=2;
    for(int i=0;i<e[nw].size();i++){
        int v=e[nw][i].first;
        int w=e[nw][i].second;
        if(rdis[v]>rdis[nw]+w){
            rdis[v]=rdis[nw]+w;
            pq.push({rdis[v],v});
        }
    }
}
return dis[n]+rdis[1];
}
vector<int>ee[210];
vector<int>er[210];

int dis1[210];int frm[210];
int rdis1[210];int frmn[210];

int disn[210];
int rdisn[210];

int fdis[210][210];
int isin[50010];
signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>m;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            fdis[i][j]=1e18;
        }
        fdis[i][i]=0;
    }

    for(int i=1;i<=m;i++){
        cin>>uar[i]>>var[i]>>war[i]>>dar[i];
        ee[uar[i]].push_back(i);
        er[var[i]].push_back(i);
        fdis[uar[i]][var[i]]=min(fdis[uar[i]][var[i]],war[i]);
    }
    for(int i=1;i<=n;i++){
        dis1[i]=1e18;
        rdis1[i]=1e18;
        disn[i]=1e18;
        rdisn[i]=1e18;
    }

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    dis1[1]=0;
    pq.push({0,1});
    while(pq.size()){
        int nw=pq.top().second;
        pq.pop();
        if(vis[nw]){continue;}
        vis[nw]=1;
        for(int i=0;i<ee[nw].size();i++){
            int id=ee[nw][i];
            int v=var[id];int w=war[id];
            if(dis1[v]>dis1[nw]+w){
                dis1[v]=dis1[nw]+w;
                frm[v]=id;
                pq.push({dis1[v],v});
            }
        }
    }
    for(int i=1;i<=n;i++){
        vis[i]=0;
    }
    disn[n]=0;
    pq.push({0,n});
    while(pq.size()){
        int nw=pq.top().second;
        pq.pop();
        if(vis[nw]){continue;}
        vis[nw]=1;
        for(int i=0;i<ee[nw].size();i++){
            int id=ee[nw][i];
            int v=var[id];int w=war[id];
            if(disn[v]>disn[nw]+w){
                disn[v]=disn[nw]+w;
                frmn[v]=id;
                pq.push({disn[v],v});
            }
        }
    }


    for(int i=1;i<=n;i++){
        for(int a=1;a<=n;a++){
            for(int b=1;b<=n;b++){
                fdis[a][b]=min(fdis[a][b],fdis[a][i]+fdis[i][b]);
            }
        }
    }
    if(dis1[n]<1e18){
    int nw=n;
    while(nw!=1){
        int id=frm[nw];
        isin[id]=1;
        nw=uar[id];
    }
    }
    if(disn[1]<1e18){
    int nw=1;
    while(nw!=n){
        int id=frmn[nw];
        isin[id]=1;
        nw=uar[id];
    }
    }

    int ans=dijkstera();
//cout<<"hihi\n";
    for(int i=1;i<=m;i++){
   //         cout<<i<<" ";
        if(1){
            swap(uar[i],var[i]);
            ans=min(ans,dijkstera()+dar[i]);
            swap(uar[i],var[i]);
        }
      //  continue;
        if(!isin[i]){
            int a=uar[i];int b=var[i];
            int cal=dis1[n]+fdis[n][b]+fdis[a][1]+war[i];
            cal=min(cal,disn[1]+fdis[1][b]+fdis[a][n]+war[i] );
            ans=min(ans,cal+dar[i]);

        }
        //}
    //    cout<<ans<<endl;
    }
    if(ans>=1e18){ans=-1;}
cout<<ans<<endl;



}

Compilation message

ho_t4.cpp: In function 'long long int dijkstera()':
ho_t4.cpp:31:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
ho_t4.cpp:49:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:106:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int i=0;i<ee[nw].size();i++){
      |                     ~^~~~~~~~~~~~~~
ho_t4.cpp:126:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for(int i=0;i<ee[nw].size();i++){
      |                     ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 724 KB Output is correct
2 Correct 10 ms 724 KB Output is correct
3 Correct 61 ms 784 KB Output is correct
4 Correct 64 ms 784 KB Output is correct
5 Correct 21 ms 468 KB Output is correct
6 Correct 10 ms 724 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 12 ms 468 KB Output is correct
10 Correct 84 ms 812 KB Output is correct
11 Correct 76 ms 804 KB Output is correct
12 Correct 77 ms 804 KB Output is correct
13 Correct 37 ms 724 KB Output is correct
14 Correct 45 ms 724 KB Output is correct
15 Correct 43 ms 1036 KB Output is correct
16 Correct 46 ms 724 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 4948 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 724 KB Output is correct
2 Correct 14 ms 728 KB Output is correct
3 Execution timed out 1085 ms 3704 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 724 KB Output is correct
2 Correct 10 ms 724 KB Output is correct
3 Correct 61 ms 784 KB Output is correct
4 Correct 64 ms 784 KB Output is correct
5 Correct 21 ms 468 KB Output is correct
6 Correct 10 ms 724 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 12 ms 468 KB Output is correct
10 Correct 84 ms 812 KB Output is correct
11 Correct 76 ms 804 KB Output is correct
12 Correct 77 ms 804 KB Output is correct
13 Correct 37 ms 724 KB Output is correct
14 Correct 45 ms 724 KB Output is correct
15 Correct 43 ms 1036 KB Output is correct
16 Correct 46 ms 724 KB Output is correct
17 Execution timed out 1077 ms 4948 KB Time limit exceeded
18 Halted 0 ms 0 KB -