poj2502最短路，WA到吐血，感觉米错误，大牛帮忙看看
发布网友
发布时间：2022-04-21 05:14
共1个回答
热心网友
时间：2022-06-18 04:10
1 1 10001 10001
2777 886 7793 6915 5386 8335 69 492 2362 1421 8690 27 7763 59 540 3926 9172 3426 5211 5736 2567 5368 5782 29 2862 1530 4067 5123 3929 3135 4022 9802 3069 3058 1393 8167 5011 8456 6229 8042 4421 7373 3784 4919 5198 8537 8315 4324 13 4370 6091 3526 9956 80 6862 1873 6996 9170 2305 7281 7084 925 336 6327 846 6505 1313 1729 6124 5857 9582 35 8814 545 5434 3367 4043 3 1087 3750 7276 6808 5788 7178 5403 3584 2754 2651 9932 2399 9676 5060 7739 3368 6226 12 8094 8586 795 7539 1434 570 7467 378 97 6601 3317 2902 6652 492 7301 756 4286 280 3865 9441 8444 96 8440 6619 8031 4729 8097 8117 4481 5771 709 675 4567 27 9497 7856 4586 2353 5306 6965 6219 4683 1528 8624 5732 2871 9503 8829 8270 19 9708 3368 6340 6715 7796 8149 2618 723 2846 2245 2921 3451 2379 3555 77 7488 9841 8228 5193 2350 7034 1500 124 77 6987 4914 3743 5856 2227 91 9859 8365 1432 1936 37 2551 3275 9228 1474 5407 8858 6121 6029 4395 8235 1237 5818 3793 6143 4428 5928 1011 8776 9529 4443 2404 4613 5763 8606 4538 2904 6840 5128 4818 7369 688 9917 7917 3324 6996 9470 7743 8490 2183 9772 5499 54 6725 7505 5590 2954 8139 7669 9786 8542 8082 197 84 9355 9507 6348 8804 3622 8611 9299 7828 5746 7343 4340 5568 3311 5422 7605 3810 5661 1801 4878 3730 9320 1305 9444 8736 8522 8626 6708 3465 8282 3416 2924 3258 2062 7637 2600 5624 3452 2036 9379 19 7468 5550 973 71 3881 7131 33 4930 8660 54 7199 163 89 7981 2959 2996 2813 3773 7190 9668 2926 1095 5084 66 2090 1340 3376 7684 5936 5542 7445 9107 9179 9756 6887 8418 3348 9412 1659 2172 2336 2009 6342 5210 8206 7587 7713 9301 5321 7372 4819 1255 7721 4599 5939 9904 -1 -1
5667 3940 6228 1705 9150 1127 6658 5984 9224 3920 7269 2422 4081 1396 84 5630 1972 9292 3850 7672 5385 7625 9299 1222 6042 60 713 38 6190 2298 -1 -1
8209 2590 8819 8581 7732 9336 5994 1155 -1 -1
4769 379 1776 5273 7255 8850 8142 1860 5884 5579 3205 1993 -1 -1
2504 9567 1961 613 1326 2754 44 4259 3202 8202 6784 3506 2842 2021 -1 -1
51 9528 9908 8872 -1 -1
------------------------
这组数据输出应该是36你的是29
附我AC的程序你自己查错误吧
#include <stdio.h>
#include <math.h>
#define INF 2100000000
struct point
{
int x, y;
};
point pt[300];
int no;
double map[301][301];
double dist[301];
int get_id(point t)
{
int i;
for(i = 0; i < no; i++)
{
if(t.x==pt[i].x&&t.y==pt[i].y)
return i;
}
pt[no] = t;
return no++;
}
double min(double a,double b)
{
return a-b>0?b:a;
}
double dis(int a,int b)
{
return sqrt((pt[a].x-pt[b].x)*(pt[a].x-pt[b].x)+(pt[a].y-pt[b].y)*(pt[a].y-pt[b].y));
}
void dijkstra()
{
int i, j, w;
int s[301];
for(i = 1; i <= no; i++)
{
dist[i] = map[i][0];
s[i] = 0;
}
s[0] = 1;dist[0] = 0;
for(i = 0; i < no-1; i++)
{
double min = INF;
int u;
for(j = 0; j < no; j++)
{
if(!s[j]&&dist[j]<min)
{
u = j;
min = dist[j];
}
}
s[u] = 1;
for(w = 0; w < no; w++)
{
if(!s[w] && map[u][w] < INF && dist[w]>map[u][w]+dist[u])
{
dist[w] = map[u][w]+dist[u];
}
}
}
printf("%.0lf\n",dist[no-1]);
}
int main()
{
int i, j;
int id, n;
int line[201];
point st, ed, tmp;
scanf("%d%d%d%d",&st.x,&st.y,&ed.x,&ed.y);
no = 0;
pt[no++] = st;
for(i = 0; i < 300; i++)
for(j = 0; j < 300; j++)
map[i][j] = INF;
while(scanf("%d%d",&tmp.x,&tmp.y)==2)
{
n = 0;
while(tmp.x!=-1&&tmp.y!=-1)
{
id = get_id(tmp);
line[n++] = id;
scanf("%d%d",&tmp.x,&tmp.y);
}
for(i = 1; i < n; i++)
{
map[line[i-1]][line[i]] = dis(line[i-1],line[i])*60.0/40000.0;
map[line[i]][line[i-1]] = map[line[i-1]][line[i]];
}
}
get_id(ed);
for(i = 0; i < no; i++)
for(j = i+1; j < no; j++)
{
map[i][j] = min(60.0*dis(j,i)/10000.0,map[i][j]);
map[j][i] = map[i][j];
}
dijkstra();
return 0;
}
