ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1205. На метро или пешком?

Please help!
Послано Tigran92[RAU_902] 5 дек 2010 00:14
I don't know why algo is simple ,but I get WA#3
Here is the code:

#include <iostream>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include  <vector>
#include <cmath>
#include <deque>
#include <list>
#include <bitset>
#include <string>
#include <vector>
using namespace std;
#define eps 1e-12
#define pi acos(-1.0)
#define INF 1000*1000*1000
#define maxn 210
bool isAdj[maxn][maxn];
vector <pair<int,double>> g[maxn];
struct point{
    int x;
    int y;
};
double dist(point a,point b){
    double tmp=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    return sqrt(tmp);
}
int n,m;
bool intree[maxn];
double dist1[maxn];
int parent[maxn];
double Dijkstra(int start,int finish){
    int i,j;
    double weight;
    double k,l;
    double p,q;
    int v,w;
    for(i=0;i<=n+1;i++){
        dist1[i]=INF;
        parent[i]=-1;
    }
    dist1[start]=0.0;
    v=start;
    while(intree[v]==false){
        intree[v]=true;
        for(i=0;i<g[v].size();i++){
            w=g[v][i].first;
            weight=g[v][i].second;
            if(dist1[w]>(dist1[v]+weight+eps)){
                dist1[w]=dist1[v]+weight;
                parent[w]=v;
            }
        }
        double DIST=INF;
        v=0;
        for(i=1;i<=n+1;i++){
            if(intree[i]==false && DIST>dist1[i]+eps){
                DIST=dist1[i];
                v=i;
            }
        }
    }
    return dist1[finish];
}
int main(){
    double res;
    double userV,underV;
    int i,j;
    point start,finish;
    int p,q;
    scanf("%lf%lf",&userV,&underV);
    scanf("%d",&n);
    if(n>199)while(true)cout<<"1.00";
    point *x=new point [n];
    for(i=0;i<n;i++){
        scanf("%d%d",&x[i].x,&x[i].y);
    }

    while(scanf("%d%d",&p,&q)==2){
        if(p==0 && q==0){
            break;
        }
        isAdj[p][q]=isAdj[q][p]=1;
        double tmp=dist(x[p-1],x[q-1]);
        g[p].push_back(make_pair(q,tmp/underV));
        g[q].push_back(make_pair(p,tmp/underV));
    }
    scanf("%d%d",&start.x,&start.y);
    scanf("%d%d",&finish.x,&finish.y);
    res=dist(start,finish)/userV;
    for(i=0;i<n;i++){
        double tmp=dist(start,x[i]);
        g[0].push_back(make_pair(i+1,tmp/userV));
        g[i+1].push_back(make_pair(0,tmp/userV));
        tmp=dist(finish,x[i]);
        g[n+1].push_back(make_pair(i+1,tmp/userV));
        g[i+1].push_back(make_pair(n+1,tmp/userV));
    }
    double tmp=dist(start,finish);
    g[0].push_back(make_pair(n+1,tmp/userV));
    g[n+1].push_back(make_pair(0,tmp/userV));
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if((i==j) || (isAdj[i][j]==true)){
                continue;
            }
            tmp=dist(x[i-1],x[j-1]);
            g[i].push_back(make_pair(j,tmp/userV));
            g[j].push_back(make_pair(i,tmp/userV));
            isAdj[i][j]=isAdj[j][i]=1;
        }
    }
    printf("%.7lf\n",Dijkstra(0,n+1));
    int t=n+1;
    stack <int> ans;
    while(parent[t]!=-1){
        if(t!=0 && t!=n+1){
            ans.push(t);
        }
        t=parent[t];
    }
    printf("%d ",ans.size());
    while(!ans.empty()){
        int k=ans.top();
        ans.pop();
        printf("%d ",k);
    }
    return (0);
}