做的第一道图论题,用的是Dijkstra单源最短路算法,给我带来了无比沉痛的回忆啊!!!!WA了20+次,不知道错在哪里,最后换C++交,竟然AC了,poj各种坑啊
找的原因了 ,G++在poj上不能用%lf 而应该是%f
下面是code: 顺便求解。。。。。
#include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define Si set<int> #define LL long long #define pb push_back #define PS printf(" ") #define Vi vector<int> #define LN printf("\n") #define lson l,m,rt << 1 #define rson m+1,r,rt<<1|1 #define SD(a) scanf("%d",&a) #define PD(a) printf("%d\n",a) #define SET(a,b) memset(a,b,sizeof(a)) #define FF(i,a) for(int i(0);i<(a);i++) #define FD(i,a) for(int i(a);i>=(1);i--) #define FOR(i,a,b) for(int i(a);i<=(b);i++) #define FOD(i,a,b) for(int i(a);i>=(b);i--) #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) const int maxn = 205; const int INF = ~0U>>1; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; const double pi = acos(-1.0); using namespace std; struct point{ int x,y; }p[maxn]; int cnt; bool vis[maxn]; double dis[maxn],edge[maxn][maxn]; double GetDis(point a,point b) { return sqrt(double((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))); } double Dijkstra(){ double min; int k;//扩展点 FOR(i,2,cnt) dis[i]=edge[1][i]; dis[1]=0; //源顶点到源顶点的距离为0 vis[1]=true; FOR(i,2,cnt){ min=INF; FOR(j,1,cnt){ if(!vis[j] && dis[j] <min){ min=dis[j]; k=j; } } vis[k]=true; FOR(j,1,cnt){ if(!vis[j] && dis[j]>dis[k]+edge[k][j]) dis[j]=dis[k]+edge[k][j]; } } return dis[2]; } int main() { cnt=3; double ans,td; bool flag=false; memset(edge, 0, sizeof(edge)); memset(vis, false, sizeof(vis)); scanf("%d%d%d%d",&p[1].x,&p[1].y,&p[2].x,&p[2].y); while(~scanf("%d%d",&p[cnt].x,&p[cnt].y)){ if(p[cnt].x==-1&&p[cnt].y==-1){ flag=false; continue; } if(flag){ td=GetDis(p[cnt],p[cnt-1]); edge[cnt][cnt-1]=edge[cnt-1][cnt]=td/2000*3; //国际惯例,先除后乘 } flag=true; cnt++; } cnt--; //然后求出非地铁线上的点的时间权 FOR(i,1,cnt) FOR(j,i+1,cnt){ if(edge[i][j]==0.0){ td=GetDis(p[i],p[j]); edge[i][j]=edge[j][i]=td/500*3; } } printf("%0.0lf\n",Dijkstra()); return 0; }