#include <bits/stdc++.h> #define ll long long #define sz(x) (int)x.size() using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll n, m, k; cin >> n >> m >> k; vector<string> s(n); for(int i = 0; i < n; i++) { cin >> s[i]; } ll a, b; cin >> a >> b; vector<vector<vector<pair<ll, pair<ll, ll> > > > > g(n, vector<vector<pair<ll, pair<ll, ll> > > >(m, vector<pair<ll, pair<ll, ll> > >())); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(i + 1 < n && s[i + 1][j] == '.') g[i][j].push_back({a, {i + 1, j}}); if(j + 1 < m && s[i][j + 1] == '.') g[i][j].push_back({a, {i, j + 1}}); if(i - 1 >= 0 && s[i - 1][j] == '.') g[i][j].push_back({b, {i - 1, j}}); if(j - 1 >= 0 && s[i][j - 1] == '.') g[i][j].push_back({b, {i, j - 1}}); } } vector<vector<ll> > dists(n, vector<ll>(m, 1000000000000000000)); dists[0][0] = 0; priority_queue<pair<ll, pair<ll, ll> > > pq; vector<vector<bool> > visited(n, vector<bool>(m, 0)); pq.push({0, {0, 0}}); while(!pq.empty()) { pair<ll, ll> act = pq.top().second; visited[act.first][act.second] = 1; pq.pop(); for(pair<ll, pair<ll, ll> > v : g[act.first][act.second]) { if(dists[v.second.first][v.second.second] > dists[act.first][act.second] + v.first) { dists[v.second.first][v.second.second] = dists[act.first][act.second] + v.first; pq.push({-v.first, {v.second.first, v.second.second}}); } } } cout << dists[n - 1][m - 1] << ' ' << 1 << '\n'; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <bits/stdc++.h> #define ll long long #define sz(x) (int)x.size() using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll n, m, k; cin >> n >> m >> k; vector<string> s(n); for(int i = 0; i < n; i++) { cin >> s[i]; } ll a, b; cin >> a >> b; vector<vector<vector<pair<ll, pair<ll, ll> > > > > g(n, vector<vector<pair<ll, pair<ll, ll> > > >(m, vector<pair<ll, pair<ll, ll> > >())); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(i + 1 < n && s[i + 1][j] == '.') g[i][j].push_back({a, {i + 1, j}}); if(j + 1 < m && s[i][j + 1] == '.') g[i][j].push_back({a, {i, j + 1}}); if(i - 1 >= 0 && s[i - 1][j] == '.') g[i][j].push_back({b, {i - 1, j}}); if(j - 1 >= 0 && s[i][j - 1] == '.') g[i][j].push_back({b, {i, j - 1}}); } } vector<vector<ll> > dists(n, vector<ll>(m, 1000000000000000000)); dists[0][0] = 0; priority_queue<pair<ll, pair<ll, ll> > > pq; vector<vector<bool> > visited(n, vector<bool>(m, 0)); pq.push({0, {0, 0}}); while(!pq.empty()) { pair<ll, ll> act = pq.top().second; visited[act.first][act.second] = 1; pq.pop(); for(pair<ll, pair<ll, ll> > v : g[act.first][act.second]) { if(dists[v.second.first][v.second.second] > dists[act.first][act.second] + v.first) { dists[v.second.first][v.second.second] = dists[act.first][act.second] + v.first; pq.push({-v.first, {v.second.first, v.second.second}}); } } } cout << dists[n - 1][m - 1] << ' ' << 1 << '\n'; } |