oj.uz

Submission #747072

# Submission time Handle Problem Language Result Execution time Memory
747072 2023-05-23T15:04:45 Z 1075508020060209tc Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 4944 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&&disn[1]<1e18){

    int nw=n;
    while(nw!=1){
        int id=frm[nw];
        isin[id]=1;
        nw=uar[id];
    }
    nw=1;
    while(nw!=1){
        int id=frmn[nw];
        isin[id]=1;
        nw=uar[id];
    }
    }
//cout<<"hihi\n";

    int ans=dijkstera();
//cout<<"hihi\n";
    for(int i=1;i<=m;i++){
        if(isin[i]||1){
            swap(uar[i],var[i]);
            ans=min(ans,dijkstera()+dar[i]);
            swap(uar[i],var[i]);
        }else{
            int a=uar[i];int b=var[i];
            int cal=dis1[n]+war[i]+fdis[a][1]+fdis[n][b];
            cal=min(cal,disn[1]+war[i]+fdis[1][b]+fdis[a][n]);
            ans=min(ans,cal+dar[i]);
        }
    }
    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 44 ms 800 KB Output is correct
2 Correct 10 ms 724 KB Output is correct
3 Correct 56 ms 824 KB Output is correct
4 Correct 60 ms 724 KB Output is correct
5 Correct 19 ms 544 KB Output is correct
6 Correct 9 ms 724 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 12 ms 500 KB Output is correct
10 Correct 81 ms 804 KB Output is correct
11 Correct 76 ms 724 KB Output is correct
12 Correct 79 ms 724 KB Output is correct
13 Correct 38 ms 816 KB Output is correct
14 Correct 44 ms 724 KB Output is correct
15 Correct 40 ms 832 KB Output is correct
16 Correct 47 ms 948 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 800 KB Output is correct
2 Correct 10 ms 732 KB Output is correct
3 Execution timed out 1083 ms 3636 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 800 KB Output is correct
2 Correct 10 ms 724 KB Output is correct
3 Correct 56 ms 824 KB Output is correct
4 Correct 60 ms 724 KB Output is correct
5 Correct 19 ms 544 KB Output is correct
6 Correct 9 ms 724 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 12 ms 500 KB Output is correct
10 Correct 81 ms 804 KB Output is correct
11 Correct 76 ms 724 KB Output is correct
12 Correct 79 ms 724 KB Output is correct
13 Correct 38 ms 816 KB Output is correct
14 Correct 44 ms 724 KB Output is correct
15 Correct 40 ms 832 KB Output is correct
16 Correct 47 ms 948 KB Output is correct
17 Execution timed out 1069 ms 4944 KB Time limit exceeded
18 Halted 0 ms 0 KB -