MELE3 - MELE3
Tác giả: RR
Ngôn ngữ: C++
//Written by RR
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN 1111
#define FOR(i,a,b) for(long i=a; i<=b; i++)
#define V vector<long>
#define FORV(i,v) for(V::iterator i=v.begin(); i!=v.end(); i++)
#define PB push_back
#define MP make_pair
using namespace std;
typedef pair< long, long > ii;
long n,k,dist[MAXN];
V ke[MAXN];
priority_queue <ii,vector<ii>,greater<ii> > pq;
void inp() {
scanf("%ld %ld",&k,&n);
FOR(i,1,n) {
long u,v;
scanf("%ld %ld",&u,&v);
ke[u].PB(v);
ke[v].PB(u);
}
}
void solve() {
FOR(i,2,k) dist[i]=1000111000;
pq.push(MP(0,1));
while (!pq.empty()) {
ii top=pq.top(); pq.pop();
long v=top.second,d=top.first;
if (d<=dist[v])
FORV(u,ke[v])
if (*u>v) {
long len=*u-v;
long temp=(dist[v]/(len<<1))*len<<1; if (temp<dist[v]) temp+=len<<1;
temp+=len;
// printf("%ld -> %ld %ld\n",v,*u,temp);
if (temp<dist[*u]) {dist[*u]=temp; pq.push(MP(dist[*u],*u)); }
} else {
long len=v-*u;
long temp=((dist[v]-len)/(len<<1))*(len<<1)+len;
if (temp<dist[v]) temp+=len<<1;
temp+=len;
// printf("%ld -> %ld %ld\n",v,*u,temp);
if (temp<dist[*u]) {dist[*u]=temp; pq.push(MP(dist[*u],*u)); }
}
}
printf("%lld\n",5LL*dist[k]);
}
int main() {
#ifdef DEBUG
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
inp();
solve();
return 0;
}