結果

問題 No.3111 Toll Optimization
ユーザー rui_er
提出日時 2025-04-20 12:33:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 351 ms / 5,000 ms
コード長 3,930 bytes
コンパイル時間 2,319 ms
コンパイル使用メモリ 203,592 KB
実行使用メモリ 76,892 KB
最終ジャッジ日時 2025-04-20 12:33:40
合計ジャッジ時間 13,206 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Problem: No.3111 Toll Optimization
// Contest: yukicoder
// URL: https://yukicoder.me/problems/no/3111
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const ll N = 5e5 + 5, inf = 0x3f3f3f3f3f3f3f3fll;

ll n, m, k, ec[N], eu[N], ev[N], dis[N], vis[N];
vector<tuple<ll, ll>> e[N];

void dijkstra(ll s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    priority_queue<tuple<ll, ll>> heap;
    dis[s] = 0;
    heap.emplace(-dis[s], s);
    while(!heap.empty()) {
        ll u = get<1>(heap.top()); heap.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto [v, w] : e[u]) {
            if(dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                heap.emplace(-dis[v], v);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    rep(i, 1, m) cin >> ec[i];
    rep(i, 1, m) cin >> eu[i] >> ev[i];
    rep(t, 0, k) {
        rep(i, 1, m) {
            e[n * t + eu[i]].emplace_back(n * t + ev[i], ec[i]);
            e[n * t + ev[i]].emplace_back(n * t + eu[i], ec[i]);
            if(t < k) {
                e[n * t + eu[i]].emplace_back(n * (t + 1) + ev[i], 0);
                e[n * t + ev[i]].emplace_back(n * (t + 1) + eu[i], 0);
            }
        }
        rep(i, 1, n) {
            if(t < k) {
                e[n * t + i].emplace_back(n * (t + 1) + i, 0);
            }
        }
    }
    dijkstra(n * 0 + 1);
    cout << (dis[n * k + n] == +inf ? -1LL : dis[n * k + n]) << endl;
    return 0;
}
0