MELE3 - MELE3

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#include <climits>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 1010;
using namespace std;
int d[N];
int n, m;
VI a[N];

void dijkstra() {
    priority_queue<II, vector<II>, greater<II> > Q;
    Q.push(MP(0, 1));
    REP(i, 2, n) d[i] = INT_MAX;
    while (!Q.empty()) {
        int u = Q.top().Y, du = Q.top().X; Q.pop();
        if (du != d[u]) continue;
        if (u == n) break;
        int duu;
        FOR(i, 0, SZ(a[u])) {
            int v = a[u][i];
            int dist = abs(u - v);
            if (u < v) {
                if (du % dist == 0) duu = ((du / dist) & 1) ? du + dist : du;
                else {
                    if ((du / dist) & 1) duu = du / dist * dist + dist;
                    else duu = du / dist * dist + dist + dist;
                }
            }
            else {
                if (du % dist == 0) duu = ((du / dist) & 1) ? du : du + dist;
                else {
                    if ((du / dist) & 1) duu = du / dist * dist + dist + dist;
                    else duu = du / dist * dist + dist;
                }
            }
            if (d[v] > duu + dist) {
                d[v] = duu + dist;
                Q.push(MP(d[v], v));
            }
        }
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int u, v;
    FOR(i, 0, m) {
        cin >> u >> v;
        a[u].PB(v); a[v].PB(u);
    }
    dijkstra();
    cout << d[n] * 5;
    return 0;
}

Download