Submission #833960

#	Time	Username	Problem	Language	Result	Execution time	Memory
833960		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	72 ms	13864 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define pli pair<ll, int>
#define fi first
#define se second
using namespace std;
const ll nmax = 1e5+5;
int n, m, s, t, u, v;
vector<pli> adj[nmax];
ll du[nmax], dv[nmax], ds[nmax], dt[nmax], dp[nmax], ans;
priority_queue<pli, vector<pli>, greater<pli>> pq;

void dijkstra(int s, ll dist[nmax])
{
	memset(dist, 0x3f, sizeof(dist));
	dist[s]=0;
	pq.push({0, s});
	while(!pq.empty())
    {
		pli p=pq.top();
		pq.pop();
		int u=p.se;
		if(p.fi>dist[u])
			continue;
		for(pli e : adj[u])
		{
			int v=e.se;
			if(dist[u]+e.fi<dist[v])
			{
				dist[v]=dist[u]+e.fi;
				pq.push({dist[v], v});
			}
		}
	}
}

ll cdp(int u, bool a)
{
    if(dp[u]==-1)
    {
        if(ds[u]+dt[u]==ds[t])
        {
            dp[u]=dv[u];
			for(pli e : adj[u])
				if(a?ds[u]+e.fi == ds[e.se]:dt[u]+e.fi==dt[e.se])
					dp[u]=min(cdp(e.se, a), dp[u]);
			ans=min(du[u]+dp[u], ans);
		}
        else dp[u]=1e18;
	}
	return dp[u];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> s >> t >> u >> v, --s, --t, --u, --v;
	while(m--)
    {
		int ui, vi, wi;
		cin >> ui >> vi >> wi;
        ui--; vi--;
		adj[ui].push_back({wi, vi});
		adj[vi].push_back({wi, ui});
	}
	dijkstra(u, du);
	dijkstra(v, dv);
	dijkstra(s, ds);
	dijkstra(t, dt);
	ans=du[v];
	memset(dp, -1, 8*n);
	cdp(t, 0);
	memset(dp, -1, 8*n);
	cdp(s, 1);
	cout<<ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, long long int*)':
commuter_pass.cpp:15:28: warning: 'sizeof' on array function parameter 'dist' will return size of 'long long int*' [-Wsizeof-array-argument]
   15 |  memset(dist, 0x3f, sizeof(dist));
      |                           ~^~~~~
commuter_pass.cpp:13:25: note: declared here
   13 | void dijkstra(int s, ll dist[nmax])
      |                         ^
commuter_pass.cpp:15:21: warning: argument to 'sizeof' in 'void* memset(void*, int, size_t)' call is the same expression as the destination; did you mean to dereference it? [-Wsizeof-pointer-memaccess]
   15 |  memset(dist, 0x3f, sizeof(dist));
      |                     ^~~~~~~~~~~~

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