SPOJ MELE3

#define ll long long
#include <bits/stdc++.h>
using namespace std;

/*
Ordered set usage:
order_of_key (k) : Number of items strictly smaller than k.
find_by_order(k) : K-th element in a set (counting from zero).
*/

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int OO = 1e9;
const double EPS = 1e-9;

vector<vector<int>> graph;
int best[1001];
int k,n;

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cin >> k >> n;
    graph.resize(k+1);
    for(int i = 1; i <= k; i++) {
        best[i] = -1;
    }
    for(int i = 0; i < n; i++) {
        int a,b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    priority_queue<pair<int,int>> pq;
    pq.push({0,1});
    while(!pq.empty()) {
        pair<int,int> curr = pq.top();
        pq.pop();
        curr.first *= -1;
        if(best[curr.second] != -1) {
            continue;
        }
        best[curr.second] = curr.first;
        for(int c : graph[curr.second]) {
            if(best[c] == -1) {
                int high = max(c,curr.second);
                int low = min(c,curr.second);
                int f_num = high-low+1;
                int st_num = 2*f_num - 2;
                int st = curr.first%st_num;
                bool d = st >= st_num/2;
                int floor = (d ? high-(st-st_num/2): st+low);
                int time = curr.first + high-low;
                if(floor > curr.second && d == 0) {
                    time += high-floor + high-curr.second;
                }
                else if(floor < curr.second && d == 1) {
                    time += floor-low + curr.second-low;
                }
                else {
                    time += abs(curr.second-floor);
                }
                //cout << " at curr.second = " << curr.second << " c = " << c << " floor = " << floor << " d = " << d << " time = " << time << "\n";
                pq.push({-1*time,c});
            }
        }
    }
    /*for(int i = 1; i <= k; i++) {
        cout << "best of " << i << " is " << best[i] << "\n";
    }*/
    cout << best[k]*5 << "\n";
    return 0;
}