Submission #858869

#	Time	Username	Problem	Language	Result	Execution time	Memory
858869		themaver1cks	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	374 ms	25556 KiB

commuter_pass

/**
｡∠(*・ω･)っ  ⌒ 由 ~	((　,,・з・,,　))
 _Π_____。
/______/~＼
｜ 田田｜門｜
**/

#include <bits/stdc++.h>

using namespace std;

#define fori(i, l, r) for(int (i) = (l); i < (r); ++i)
#define forie(i, l, r) for (int (i) = (l); i <= (r); ++i)
#define ford(i, l, r) for (int (i) = (l); i > (r); --i)
#define forde(i, l, r) for (int (i) = (l); i >= (r); --i)
#define int long long
#define i_inf INT_MAX
#define inf LLONG_MAX
#define ii pair<int,int>
#define fi first
#define se second
#define gcd __gcd
#define lcm(x,y) x * y/ gcd(x,y)
#define pb push_back
#define sz size
#define all(x) begin(x), end(x)
#define fastio ios_base::sync_with_stdio(0); cin.tie(nullptr);
#define el "\n"
#define sp " "
//
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
// var declare
const int maxn = 2e5 + 3;
int n, m, S, T, U, V;
// ds declare
vector <ii> adj[maxn];
//
vector <int> dijkstra(int s)
{
    vector <int> dist(n, inf);
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (pq.sz())
    {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w]: adj[u])
        {
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}
//
int commuter_pass(int S, int T)
{
    auto fromS = dijkstra(S);
    auto fromT = dijkstra(T);
    auto fromU = dijkstra(U);
    auto fromV = dijkstra(V);
    vector <int> f(n, inf);
    vector <int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int x, int y){
        return fromS[x] < fromS[y];
    });
    int ans = fromU[V];
    for (auto u: order)
    {
        f[u] = min(f[u], fromU[u]);
        for (auto [v, w]: adj[u])
        {
            if (fromS[u] + w == fromS[v] && fromS[u] + w + fromT[v] == fromS[T])
            {
                f[v] = min(f[v], f[u]);
            }
        }
        if (fromS[u] + fromT[u] == fromS[T])
            ans = min(ans, f[u] + fromV[u]);
    }
    return ans;
}
//
void solve()
{
	cin >> n >> m;
	cin >> S >> T >> U >> V;
	--S, --T, --U, --V;
	forie(i, 1, m)
	{
	    int u, v, w; cin >> u >> v >> w;
	    --u, --v;
	    adj[u].emplace_back(v, w);
	    adj[v].emplace_back(u, w);
	}
	cout << min(commuter_pass(S, T), commuter_pass(T, S));
}
//
void multi_test()
{
	int t;
	cin >> t;
	while (t--) solve();
}
//
int32_t main()
{
	fastio;
	solve();
	return 0;
}

/**

**/

Compilation message (stderr)

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:13:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define forie(i, l, r) for (int (i) = (l); i <= (r); ++i)
      |                                 ^
commuter_pass.cpp:96:2: note: in expansion of macro 'forie'
   96 |  forie(i, 1, m)
      |  ^~~~~

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