Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
楼上为何说不是最短路呢,不解,我是来贴代码的#include<iostream> #include<queue> #include<cmath> using namespace std; #define SIZE 100000 #define More(x,y) ((x-y)>1e-8) #define Less(x,y) ((y-x)>1e-8) #define Equl(x,y) (fabs(x-y)<1e-8) #define Maxn(x,y) (More((x),(y))?(x):(y)) int times=1; int t,n; int x,y,z; int c[500][500]; double dist[SIZE]; bool inqueue[SIZE]; struct node { int v; double w; }edge[SIZE]; int index,pre[SIZE],next[SIZE]; void clear(void) { index=0; memset(pre,-1,sizeof(pre)); memset(next,-1,sizeof(next)); } void add(int u,int v,double w) { edge[index].v=v; edge[index].w=w; next[index]=pre[u]; pre[u]=index++; } queue<int> open; void Init(int s) { memset(dist,0x7f,sizeof(dist)); memset(inqueue,false,sizeof(inqueue)); dist[s]=0; open.push(s); } void SPFA(int s) { Init(s); while(!open.empty()) { int u=open.front(); open.pop(); inqueue[u]=false; for(int i=pre[u];i!=-1;i=next[i]) { int v=edge[i].v; double w=edge[i].w; if(More(dist[v],Maxn(w,dist[u]))) { dist[v]=Maxn(w,dist[u]); if(!inqueue[v]) { inqueue[v]=true; open.push(v); } } } } } double findAns(void) { SPFA(0); return dist[1]; } int main() { while(scanf("%d",&n),n) { clear(); for(int i=0;n-i>0;i++) { scanf("%d %d",&x,&y); c[i][0]=x; c[i][1]=y; for(int j=0;i-j>0;j++) { double len=sqrt((c[j][0]-c[i][0])*1.0*(c[j][0]-c[i][0])+(c[j][1]-c[i][1])*1.0*(c[j][1]-c[i][1])); add(i,j,len); add(j,i,len); } } printf("Scenario #%d\n",times++); printf("Frog Distance = %.3lf\n\n",findAns()); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator