Submission #851855

#	Time	Username	Problem	Language	Result	Execution time	Memory
851855		themaver1cks	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	563 ms	262144 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 = 1e5 + 3;
const int i_inf = 1e9;
int n, m, s, t, x, y;
// ds declare
vector <ii> adj[maxn];
vector<vector<int>> path;
vector <int> p[maxn];
//
void dijkstra()
{
    priority_queue <ii, vector<ii>, greater<ii>> pq;
    pq.push({0, s});
    vector <int> d(n+3, i_inf);
    d[s] = 0;
    while (pq.sz())
    {
        int e = pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        if (e != d[u]) continue;
        for (ii edge: adj[u])
        {
            int v = edge.fi, w = edge.se;
            if (d[v] > d[u] + w)
            {
                p[v].clear();
                p[v].pb(u);
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
            else if (d[v] == d[u] + w) p[v].pb(u);
        }
    }
}
//
void dewey(vector<int>& trace, int node)
{
    if (node == s)
    {
        path.pb(trace);
        return;
    }
    for (int v: p[node])
    {
        trace.pb(v);
        dewey(trace, v);
        trace.pop_back();
    }
}
//
void solve()
{
	cin >> n >> m >> s >> t >> x >> y;
	forie(i, 1, m)
	{
	    int u, v, w; cin >> u >> v >> w;
	    adj[u].pb({v, w});
	    adj[v].pb({u, w});
	}
	dijkstra();
	vector <int> trace;
	trace.pb(t);
	for (int v: p[t])
    {
        trace.pb(v);
        dewey(trace, v);
        trace.pop_back();
    }
    int ans = i_inf;
    for (vector<int>& a: path)
    {
        reverse(a.begin(), a.end());
        fori(i, 1, a.sz())
        {
            int u = a[i-1], v = a[i];
            adj[u].pb({v, 0});
            adj[v].pb({u, 0});
        }
        priority_queue <ii, vector<ii>, greater<ii>> pq;
        vector <int> dis(n+3, i_inf);
        dis[x] = 0;
        pq.push({0, x});
        while (pq.sz())
        {
            int e = pq.top().fi;
            int u = pq.top().se;
            pq.pop();
            if (e != dis[u]) continue;
            for (int i = adj[u].sz()-1; i >= 0; --i)
            {
                int v = adj[u][i].fi, w = adj[u][i].se;
                if (dis[v] > dis[u] + w)
                {
                    dis[v] = dis[u] + w;
                    pq.push({dis[v], v});
                }
            }
        }
        ans = min(ans, dis[y]);
        fori(i, 1, a.sz())
        {
            adj[a[i-1]].pop_back();
            adj[a[i]].pop_back();
        }
    }
    cout << ans;
}
//
void multi_test()
{
	int t;
	cin >> t;
	while (t--) solve();
}
//
int32_t main()
{
	fastio;
	solve();
	return 0;
}

/**
5 7
1 3
4 5
1 2 10
1 3 30
1 4 15
2 3 10
4 3 5
3 5 10
4 5 12
**/

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:87:2: note: in expansion of macro 'forie'
   87 |  forie(i, 1, m)
      |  ^~~~~
commuter_pass.cpp:12:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define fori(i, l, r) for(int (i) = (l); i < (r); ++i)
      |                               ^
commuter_pass.cpp:106:9: note: in expansion of macro 'fori'
  106 |         fori(i, 1, a.sz())
      |         ^~~~
commuter_pass.cpp:12:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define fori(i, l, r) for(int (i) = (l); i < (r); ++i)
      |                                            ^
commuter_pass.cpp:106:9: note: in expansion of macro 'fori'
  106 |         fori(i, 1, a.sz())
      |         ^~~~
commuter_pass.cpp:12:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define fori(i, l, r) for(int (i) = (l); i < (r); ++i)
      |                               ^
commuter_pass.cpp:133:9: note: in expansion of macro 'fori'
  133 |         fori(i, 1, a.sz())
      |         ^~~~
commuter_pass.cpp:12:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define fori(i, l, r) for(int (i) = (l); i < (r); ++i)
      |                                            ^
commuter_pass.cpp:133:9: note: in expansion of macro 'fori'
  133 |         fori(i, 1, a.sz())
      |         ^~~~

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