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> // Dij ²¢²»ÄÜÈÃ×ܳ¤×îС£¬ÊÇ´íÎóµÄ #include <vector> #include <cmath> using namespace std; struct Point { int x,y; }; Point d[101]; vector <int> v[101]; double Dij[101]; double dis[101][101]; int N,M; const double INF = 99999999999999.0; bool vis[101]; void init() { for( int i=1; i<N; i++) { for(int j=i+1; j<=N;j++) { dis[i][j] = sqrt( (d[i].x-d[j].x)*(d[i].x-d[j].x) + (d[i].y-d[j].y)*(d[i].y-d[j].y) ); dis[j][i] = dis[i][j]; } dis[i][i] = 0.0; } for(i=1; i<=N;i++) Dij[i] = INF; Dij[1] = 0.0; vector <int>::iterator ptr = v[1].begin(); int b; while( ptr != v[1].end()) { b = *ptr; Dij[b] = dis[1][b]; ptr++; } memset(vis,0,sizeof(vis)); } void work() { init(); vector<int>::iterator ptr,pend; double min; int p,j,b; double rst =0.0; for(int i=1;i<=N;i++) { min =INF; p=-1; for(j=1;j<=N;j++) { if(!vis[j] && Dij[j] < min) { min = Dij[j]; p = j; } } rst += min; if( p==-1) break; vis[p] = true; ptr = v[p].begin(); pend = v[p].end(); while( ptr != pend) { b = *ptr; if(!vis[b] && Dij[b] > dis[p][b] ) Dij[b] = dis[p][b]; ptr++; } } if( p==-1) printf("poor snoopy\n"); else printf("%.2lf\n",rst); } int main() { // freopen("C:\\ACMData.txt","r",stdin); int i,a,b; while( scanf("%d%d",&N,&M) != EOF) { for(i=1;i<=N;i++) { scanf("%d%d", &d[i].x,&d[i].y); v[i].clear(); } for(i=1;i<=M;i++) { scanf("%d%d",&a,&b); v[a].push_back(b); } work(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator