oj.uz

Submission #747105

# Submission time Handle Problem Language Result Execution time Memory
747105 2023-05-23T16:00:13 Z 1075508020060209tc Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 48 ms 5548 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){
    cout<<-1;return 0;
}
    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];
    }
    }
//cout<<"hihi\n";

    int ans=dijkstera();
//cout<<"hihi\n";
    for(int i=1;i<=m;i++){
   //         cout<<i<<" ";
        if(isin[i]){
            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]+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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 724 KB Output is correct
2 Correct 9 ms 616 KB Output is correct
3 Correct 11 ms 748 KB Output is correct
4 Correct 11 ms 724 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 9 ms 732 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 26 ms 724 KB Output is correct
11 Correct 44 ms 828 KB Output is correct
12 Correct 32 ms 828 KB Output is correct
13 Incorrect 10 ms 744 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5548 KB Output is correct
2 Correct 36 ms 5452 KB Output is correct
3 Correct 48 ms 5412 KB Output is correct
4 Correct 10 ms 852 KB Output is correct
5 Correct 10 ms 744 KB Output is correct
6 Correct 8 ms 724 KB Output is correct
7 Correct 10 ms 724 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 30 ms 4148 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 744 KB Output is correct
2 Correct 11 ms 724 KB Output is correct
3 Correct 30 ms 4336 KB Output is correct
4 Correct 9 ms 724 KB Output is correct
5 Correct 29 ms 5272 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 28 ms 4456 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 724 KB Output is correct
2 Correct 9 ms 616 KB Output is correct
3 Correct 11 ms 748 KB Output is correct
4 Correct 11 ms 724 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 9 ms 732 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 26 ms 724 KB Output is correct
11 Correct 44 ms 828 KB Output is correct
12 Correct 32 ms 828 KB Output is correct
13 Incorrect 10 ms 744 KB Output isn't correct
14 Halted 0 ms 0 KB -