讨论 / 你说我WA我都认了.但不能说我没输出..
搁浅 2010-05-12 21:53:00
点我顶贴 收藏 删除
#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#define INF 0x7fffffff

using namespace std;

struct point{

double x,y;

}p[101];

int N;

double V;

int links[101][101],f[101];

double dis[101][101] , d[101] ;

void dij(){

int q[10000] , visit[101];

int tail , head ;

q[++head] = 1;

for (int i = 2 ; i <= N ; i++)

{

double Mindis = INF;

int k ;

for (int j = 2 ; j <= N ; j++)

if (dis[1][j] < Mindis && visit[j]==false)

{

Mindis = dis[1][j];

k = j;

}

visit[k] = true;

for (int j = 1 ; j <= N ; j++)

if (dis[1][k] + dis[k][j] < dis[1][j] && visit[j]==false)

{

dis[1][j] = dis[1][k] + dis[k][j];

}

}

}

int main(){

//freopen("tmp.in","r",stdin);

//freopen("tmp.out","w",stdout);

scanf("%d%lf",&N,&V);

for (int i = 1 ; i <= N ; i++)

for (int j = 1 ; j <= N ; j++)

if (i!=j)

dis[i][j] = INF;

for (int i = 1 ; i <= N ; i++)

{

scanf("%lf%lf%d",&p[i].x,&p[i].y,&f[i]);

links[f[i]][0]++;

links[f[i]][links[f[i]][0]] = i;

dis[f[i]][i] = sqrt((p[i].x - p[f[i]].x)*(p[i].x - p[f[i]].x)+(p[i].y - p[f[i]].y)*(p[i].y - p[f[i]].y));

dis[f[i]][i] /= V;

}

for (int u = 1 ; u <= N ; u++)

for (int v = 1 ; v <= N ; v++)

{

if (p[u].x == p[v].x && p[u].y > p[v].y)

{

links[u][++links[u][0]] = v;

dis[u][v] = min(dis[u][v] , sqrt(((p[u].y - p[v].y)*2)/double(10)));

}

}

dij();

printf("%.2lf\n",dis[1][N]);

return 0;

}

#1 idota@2010-05-12 21:53:00
回复 删除
崩溃了?
查看更多回复
提交回复