제출 #1109024

#제출 시각아이디문제언어결과실행 시간메모리
1109024vjudge1Pohlepko (COCI16_pohlepko)C++17
20 / 80
709 ms65536 KiB
#include <bits/stdc++.h> #define F first #define S second #define LL long long #define rep(i, x) for(auto &i : (x)) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define left(x) ((x)<<1) #define right(x) ((x)>>1) #define LSOne(x) (x & -(x)) using namespace std; using T = pair<int, pair<int, int>>; const int SZ = 2e5 + 1; const LL MOD = 1e9 + 7; const LL INF = 1e18 + 1; LL bp (LL b, LL e, LL m = MOD) { if ( e == 0 ) return 1; LL T = bp(b, e / 2); T *= T; T %= m; if ( e & 1 ) T *= b; return T %= m; } LL nv_i (LL a) { return bp(a, MOD - 2); }; LL gcd (LL a, LL b) { return (b == 0 ? a : gcd(b, a % b)); } LL lcm(LL a, LL b) { return (a * (b / gcd(a, b))); } LL ceil (LL a, LL b) { return ((a + b - 1) / b); } vector<vector<int>> G, DIS; vector<vector<pair<int, int>>> FATHER; vector<vector<bool>> VIS; int n, m; void dijkstra() { priority_queue<T, vector<T>, greater<T>> PQ; PQ.push({0, {1, 1}}); while(!PQ.empty()) { int dist = PQ.top().F, i = PQ.top().S.F, j = PQ.top().S.S; PQ.pop(); if(VIS[i][j]) continue; VIS[i][j] = 1; if(i + 1 <= n) { if(DIS[i + 1][j] > dist + G[i][j]) { DIS[i + 1][j] = dist + G[i][j]; PQ.push({DIS[i + 1][j], {i + 1, j}}); FATHER[i + 1][j] = {i, j}; } } if(j + 1 <= m) { if(DIS[i][j + 1] > dist + G[i][j]) { DIS[i][j + 1] = dist + G[i][j]; PQ.push({DIS[i][j + 1], {i, j + 1}}); FATHER[i][j + 1] = {i, j}; } } } } void word(int i, int j) { if(i == 1 && j == 1) { cout << char(G[i][j]); return; } word(FATHER[i][j].F, FATHER[i][j].S); cout << char(G[i][j]); } void solve() { cin >> n >> m; G.resize(n + 1, vector<int> (m + 1)); DIS.resize(n + 1, vector<int> (m + 1, 1e8)); VIS.resize(n + 1, vector<bool> (m + 1)); FATHER.resize(n + 1, vector<pair<int, int>> (m + 1)); for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { char x; cin >> x; G[i][j] = int(x); } } DIS[1][1] = 0; dijkstra(); word(n, m); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...