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;
}

Download