Submission #851678

#	Time	Username	Problem	Language	Result	Execution time	Memory
851678		lftroq	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	45 ms	23468 KiB

commuter_pass

/*
                     ,
                ,.  | \
               |: \ ; :\
               :' ;\| ::\
                \ : | `::\
                _)  |   `:`.
              ,' , `.    ;: ;
            ,' ;:  ;"'  ,:: |_
           /,   ` .    ;::: |:`-.__
        _,' _o\  ,::.`:' ;  ;   . '
    _,-'           `:.          ;""\,
 ,-'                     ,:         `-;,
 \,                       ;:           ;--._
  `.______,-,----._     ,' ;:        ,/ ,  ,`
         / /,-';'  \     ; `:      ,'/,::.:::
       ,',;-'-'_,--;    ;   :.   ,',',;::::::
      ( /___,-'     `.     ;::,,'o/  ,:::::::
       `'             )    ;:,'o /  ;"-   -::
                      \__ _,'o ,'         ,::
                         ) `--'       ,..::::
      _lftroq_           ; `.        ,:::::::
                          ;  ``::.    :::::::
*/
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007LL
#define MOD2 998244353LL
#define endl '\n'
#define INFINITE 2147483647LL
#define INFINITE2 9223372036854775807
#define llll pair<ll,ll>
#define ldld pair<ld,ld>
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

ll n,m,s,t,x,y;
vector<llll> graph[100005];
ll u[100005],v[100005],w[100005],d[100005],d1[100005];

void dijkstra(ll s)
{
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    priority_queue<llll,vector<llll>,greater<llll>> pq;
    pq.push({d[s],s});
    while(pq.size())
    {
        ll u=pq.top().se;
        pq.pop();
        for(int i=0;i<graph[u].size();i++)
        {
            ll v=graph[u][i].fi,w=graph[u][i].se;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                pq.push({d[v],v});
            }
        }
    }
}

void dijkstra1(ll s)
{
    memset(d1,0x3f,sizeof(d1));
    d1[s]=0;
    priority_queue<llll,vector<llll>,greater<llll>> pq;
    pq.push({d1[s],s});
    while(pq.size())
    {
        ll u=pq.top().se;
        pq.pop();
        for(int i=0;i<graph[u].size();i++)
        {
            ll v=graph[u][i].fi,w=graph[u][i].se;
            if(d1[v]>d1[u]+w)
            {
                d1[v]=d1[u]+w;
                pq.push({d1[v],v});
            }
        }
    }
}

void solve1()
{
    dijkstra(s);
    dijkstra1(t);
    vector<bool> check(100005);
    for(int i=1;i<=m;i++)
    {
        if(d[u[i]]+d1[v[i]]+w[i]==d[t]) check[u[i]]=check[v[i]]=true;
        if(d[v[i]]+d1[u[i]]+w[i]==d[t]) check[u[i]]=check[v[i]]=true;
    }
    ll ans=INFINITE2;
    dijkstra(y);
    for(int i=1;i<=n;i++) if(check[i]) ans=min(ans,d[i]);
    cout << ans << endl;
}

void solve()
{
    cin >> n >> m >> s >> t >> x >> y;
    for(int i=1;i<=m;i++)
    {
        cin >> u[i] >> v[i] >> w[i];
        graph[u[i]].push_back({v[i],w[i]});
        graph[v[i]].push_back({u[i],w[i]});
    }
    if(s==x)
    {
        solve1();
        return;
    }
    if(s==y)
    {
        swap(x,y);
        solve1();
        return;
    }
}

int main()
{
    fastIO
    //freopen("hanhhhh.inp","r",stdin);
    //freopen("hanhhhh.out","w",stdout);
    ll t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(ll)':
commuter_pass.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int i=0;i<graph[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1(ll)':
commuter_pass.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int i=0;i<graph[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~

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