Submission #1038400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038400		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	517 ms	26408 KiB

commuter_pass

#include <bits/stdc++.h>
#define ss second
#define pb push_back
#define mod 1000000007
#define int long long
#define N 100005
#define pu push
#define ff first
#define pint pair<int,int>
 
using namespace std;

int n,m,x1,yyy,x2,y2;
int dis[N],vis[N],come[N],go[N],dp[N];
vector<pint> v[N];
vector<int> x;

inline void dijkstra(int start)
{
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<pint> pq;
    pq.pu({0,start});
    while(!pq.empty())
    {
        int ind=pq.top().ss,cost=-pq.top().ff;
        pq.pop();
        if(vis[ind])
            continue;
        vis[ind]=1;
        dis[ind]=cost;
        for(int i=0;i<v[ind].size();i++)
        {
            pq.pu({-(cost+v[ind][i].ss),v[ind][i].ff});
        }
    }
    return;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m>>x1>>yyy>>x2>>y2;
    x1--;
    x2--;
    yyy--;
    y2--;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    dijkstra(x1);
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.pu(yyy);
    set<int> st;
    while(!q.empty())
    {
        //break;
        int ind=q.front();
        q.pop();
        if(vis[ind])
            continue;
        st.insert(ind);
        vis[ind]=1;
        for(int i=0;i<v[ind].size();i++)
        {
            if(vis[v[ind][i].ff]==0&&dis[ind]==(dis[v[ind][i].ff]+v[ind][i].ss))
            {
                q.pu(v[ind][i].ff);
            }
        }
    }
    int total[n];
    for(int i=0;i<n;i++)
    {
        total[i]=0;
        for(int j=0;j<v[i].size();j++)
        {
            if(st.count(v[i][j].ff)&&(dis[i]+v[i][j].ss)==dis[v[i][j].ff])
                total[i]++;
        }
    }
    memset(vis,0,sizeof(vis));
    q.pu(yyy);
    while(!q.empty())
    {
        //break;
        int ind=q.front();
        q.pop();
        if(vis[ind])
            continue;
        x.pb(ind);
        vis[ind]=1;
        for(int i=0;i<v[ind].size();i++)
        {
            total[v[ind][i].ff]--;
            if(vis[v[ind][i].ff]==0&&dis[ind]==(dis[v[ind][i].ff]+v[ind][i].ss)&&!total[v[ind][i].ff])
            {
                q.pu(v[ind][i].ff);
            }
        }
    }
    /*for(int i=0;i<x.size();i++)
    {
        cout<<x[i]<<" ";
    }*/
    dijkstra(x2);
    for(int i=0;i<n;i++){
        come[i]=dis[i];
        dp[i]=10000000000000000;
    }
    dijkstra(y2);
    for(int i=0;i<n;i++)
        go[i]=dis[i];
    int ans=come[y2];
    for(int i=0;i<x.size();i++)
    {
        int ind=x[i];
        int now=go[ind];
        for(int j=0;j<v[ind].size();j++)
        {
            now=min(now,dp[v[ind][j].ff]);
        }
        dp[ind]=now;
        ans=min(ans,dp[ind]+come[ind]);
    }
    swap(x1,yyy);

    x.clear();
    memset(come,0,sizeof(come));
    memset(dp,0,sizeof(dp));
    memset(go,0,sizeof(go));
    dijkstra(x1);
    memset(vis,0,sizeof(vis));
    q.pu(yyy);
    st.clear();
    while(!q.empty())
    {
        //break;
        int ind=q.front();
        q.pop();
        if(vis[ind])
            continue;
        st.insert(ind);
        vis[ind]=1;
        for(int i=0;i<v[ind].size();i++)
        {
            if(vis[v[ind][i].ff]==0&&dis[ind]==(dis[v[ind][i].ff]+v[ind][i].ss))
            {
                q.pu(v[ind][i].ff);
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        total[i]=0;
        for(int j=0;j<v[i].size();j++)
        {
            if(st.count(v[i][j].ff)&&(dis[i]+v[i][j].ss)==dis[v[i][j].ff])
                total[i]++;
        }
    }
    memset(vis,0,sizeof(vis));
    q.pu(yyy);
    while(!q.empty())
    {
        //break;
        int ind=q.front();
        q.pop();
        if(vis[ind])
            continue;
        x.pb(ind);
        vis[ind]=1;
        for(int i=0;i<v[ind].size();i++)
        {
            total[v[ind][i].ff]--;
            if(vis[v[ind][i].ff]==0&&dis[ind]==(dis[v[ind][i].ff]+v[ind][i].ss)&&!total[v[ind][i].ff])
            {
                q.pu(v[ind][i].ff);
            }
        }
    }
    /*for(int i=0;i<x.size();i++)
    {
        cout<<x[i]<<" ";
    }*/
    dijkstra(x2);
    for(int i=0;i<n;i++){
        come[i]=dis[i];
        dp[i]=10000000000000000;
    }
    dijkstra(y2);
    for(int i=0;i<n;i++)
        go[i]=dis[i];
    ans=min(ans,come[y2]);
    for(int i=0;i<x.size();i++)
    {
        int ind=x[i];
        int now=go[ind];
        for(int j=0;j<v[ind].size();j++)
        {
            now=min(now,dp[v[ind][j].ff]);
        }
        dp[ind]=now;
        ans=min(ans,dp[ind]+come[ind]);
    }
    cout<<ans<<endl;

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(long long int)':
commuter_pass.cpp:32:22: 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]
   32 |         for(int i=0;i<v[ind].size();i++)
      |                     ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:72:22: 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]
   72 |         for(int i=0;i<v[ind].size();i++)
      |                     ~^~~~~~~~~~~~~~
commuter_pass.cpp:84:22: 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]
   84 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp:101:22: 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]
  101 |         for(int i=0;i<v[ind].size();i++)
      |                     ~^~~~~~~~~~~~~~
commuter_pass.cpp:123:18: 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]
  123 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
commuter_pass.cpp:127:22: 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]
  127 |         for(int j=0;j<v[ind].size();j++)
      |                     ~^~~~~~~~~~~~~~
commuter_pass.cpp:153:22: 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]
  153 |         for(int i=0;i<v[ind].size();i++)
      |                     ~^~~~~~~~~~~~~~
commuter_pass.cpp:164:22: 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]
  164 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp:181:22: 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]
  181 |         for(int i=0;i<v[ind].size();i++)
      |                     ~^~~~~~~~~~~~~~
commuter_pass.cpp:203:18: 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]
  203 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
commuter_pass.cpp:207:22: 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]
  207 |         for(int j=0;j<v[ind].size();j++)
      |                     ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45