oj.uz

Submission #747077

# Submission time Handle Problem Language Result Execution time Memory
747077 2023-05-23T15:10:34 Z 1075508020060209tc Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 5172 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!=n){
        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(1){
            swap(uar[i],var[i]);
            ans=min(ans,dijkstera()+dar[i]);
            swap(uar[i],var[i]);
        }//else{
        continue;
          if(!isin[i]){  
            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 42 ms 820 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 69 ms 800 KB Output is correct
4 Correct 59 ms 812 KB Output is correct
5 Correct 20 ms 468 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 340 KB Output is correct
10 Correct 81 ms 808 KB Output is correct
11 Correct 81 ms 820 KB Output is correct
12 Correct 81 ms 800 KB Output is correct
13 Correct 36 ms 804 KB Output is correct
14 Correct 43 ms 788 KB Output is correct
15 Correct 40 ms 812 KB Output is correct
16 Correct 44 ms 780 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 724 KB Output is correct
2 Correct 11 ms 728 KB Output is correct
3 Execution timed out 1086 ms 3660 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 820 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 69 ms 800 KB Output is correct
4 Correct 59 ms 812 KB Output is correct
5 Correct 20 ms 468 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 340 KB Output is correct
10 Correct 81 ms 808 KB Output is correct
11 Correct 81 ms 820 KB Output is correct
12 Correct 81 ms 800 KB Output is correct
13 Correct 36 ms 804 KB Output is correct
14 Correct 43 ms 788 KB Output is correct
15 Correct 40 ms 812 KB Output is correct
16 Correct 44 ms 780 KB Output is correct
17 Execution timed out 1060 ms 5172 KB Time limit exceeded
18 Halted 0 ms 0 KB -