Submission #169166

#	Time	Username	Problem	Language	Result	Execution time	Memory
169166		HuyQuang_re_Zero	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	581 ms	33520 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
struct pt { int u; long long k; };
pt h[100001];
long long f[100001][4],dp[100001][2],kq;
vector <int> a[100001],b[100001],c[100001],cb[100001],topo;
int n,m,u,v,i,j,k,u0,u1,u2,u3,nh,vt[100001],d[100001];
const long long oo=round(1e18);
void up(int u)
{
    while(1)
    {
        int p=u/2;
        if(p==0 || h[p].k<h[u].k) break;
        swap(vt[h[u].u],vt[h[p].u]);
        swap(h[u],h[p]);
        u=p;
    }
}
void down(int u)
{
    while(1)
    {
        int p=u*2;
        if(p<nh && h[p+1].k<h[p].k) p++;
        if(p>nh || h[p].k>h[u].k) break;
        swap(vt[h[u].u],vt[h[p].u]);
        swap(h[u],h[p]);
        u=p;
    }
}
void push(int u,long long k)
{
    h[++nh]={ u,k }; vt[u]=nh;
    up(nh);
}
void pop()
{
    swap(h[1],h[nh--]); vt[h[1].u]=1;
    down(1);
}
void dijkstra(int s,int j)
{
    nh=0;
    memset(vt,0,sizeof(vt));
    for(u=1;u<=n;u++) f[u][j]=oo;
    f[s][j]=0; push(s,j);
    while(nh>0)
    {
        int u=h[1].u; pop();
        for(int i=0;i<a[u].size();i++)
        {
            int v=a[u][i];
            if(f[v][j]>f[u][j]+c[u][i])
            {
                f[v][j]=f[u][j]+c[u][i];
                if(vt[v]==0) push(v,f[v][j]);
                else { h[vt[v]].k=f[v][j]; up(vt[v]); }
            }
        }
    }
}
void DFS(int u)
{
    d[u]=1;
    for(int i=0;i<b[u].size();i++)
    {
        int v=b[u][i];
        if(d[v]==0) DFS(v);
    }
    topo.push_back(u);
}
int main()
{
    //freopen("commuter.inp","r",stdin);
    //freopen("commuter.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>u0>>u1>>u2>>u3;
    while(m--)
    {
        cin>>u>>v>>k;
        a[u].push_back(v); a[v].push_back(u);
        c[u].push_back(k); c[v].push_back(k);
    }
    dijkstra(u0,0); dijkstra(u1,1); dijkstra(u2,2); dijkstra(u3,3);
    for(u=1;u<=n;u++)
        for(i=0;i<a[u].size();i++)
        {
            int v=a[u][i];
            if(f[u][0]+f[v][1]+c[u][i]==f[u1][0])
            {
                b[u].push_back(v);
                cb[u].push_back(c[u][i]);
            }
        }
    for(u=1;u<=n;u++)
        if(d[u]==0) DFS(u);
    kq=oo;
    for(i=0;i<topo.size();i++)
    {
        int u=topo[i];
        dp[u][0]=f[u][2]; dp[u][1]=f[u][3];
        for(int i=0;i<b[u].size();i++)
        {
            int v=b[u][i];
            dp[u][0]=min(dp[u][0],dp[v][0]);
            dp[u][1]=min(dp[u][1],dp[v][1]);
        }
        kq=min(kq,min(dp[u][0]+f[u][3],dp[u][1]+f[u][2]));
    }
    cout<<kq;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, int)':
commuter_pass.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<a[u].size();i++)
                     ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void DFS(int)':
commuter_pass.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b[u].size();i++)
                 ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<a[u].size();i++)
                 ~^~~~~~~~~~~~
commuter_pass.cpp:100:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<topo.size();i++)
             ~^~~~~~~~~~~~
commuter_pass.cpp:104:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<b[u].size();i++)
                     ~^~~~~~~~~~~~

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