dijkstra try for #1994

#include<cstdio>
#define FOR(i,a,b) for(int i=(int)a;i<=(int)b;++i)
#define REP(i,n) FOR(i,0,n-1)
#define z(i,j) ((179*(i+1)+719*(j+1))%1000)
#define INF 1<<30
int d[13010],l[13010],n,v,to,z;
char u[13010];
main(){
    scanf("%d",&n);
    REP(i,n)d[i]=INF,u[i]=false;
    d[0]=0;l[0]=0;
    REP(i,n){
        v=-1;
        REP(j,n)
            if (!u[j]&&(v==-1||d[j]<d[v])) v=j;
        u[v]=true;
        FOR(to,v+1,n-1){
            if (d[v]+z(v,to)<d[to])
                d[to]=d[v]+z(v,to),
                l[to]=l[v]+1;
        }
    }
    printf("%d",d[n-1]-500*l[n-1]);
}