[USACO Oct08 Gold] Power Failure 供電故障(pwrfail) 解題報告

【題目描述】
一場邪惡的暴風雨毀壞了農夫約翰的輸電網中的一些電綫！農夫約翰有一張包含了所有 n（2<=n<=1000）個電能中轉點的地圖，這些 點被很自然而方便的標識爲1..n，並且被整數座標x_i，y_i（-100000<=x_i<=100000;-100000& lt;=y_i<=100000）定位於座標系。

有w（1<=w<=10000）條電綫仍然保存着沒被暴風雨破壞，每條電綫連接着兩個電能中轉點pi,pj（1<=pi<=n;1<=pj<=n）。

他希望從第一個電能中轉點把電導入第n個（可能通過一些中間的電能中轉點，應當有一組電綫連接1和n）。

給出n個電能中轉點的座標和倖存的電綫，請確定最少需要架設的電綫總長度，但請注意，架設過程中，對於單條電綫而言，其長度不應超過m（0.0<=m<=200000.0）

給出一個例子，在下面，左邊是一個包含9個電能中轉電和3條倖存電綫的地圖。在這個任務中，規定名。m=2.0。最佳的架設方案是連接6和4，以及6和9。

   After the storm              Optimally reconnected
3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .
                                          /
2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .
                                        /
1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .
   |                               |
0  1 . . . . . . . . .          0  1 . . . . . . . . .

   0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9

這是的總長度是 1.414213562 + 1.414213562 = 2.828427124 .

題目名稱：pwrfail

輸入格式：

• 第一行：兩個用空格隔開的整數 n和w
• 第二行：一個實數：m
• 第3..n+2：每一行包含兩個用空格隔開的整數：x_i和y_i
• 第n+3..n+2+w行：兩個空格隔開的整數：pi和pj

輸入樣例（file pwrfail）：

9 3
2.0
0 0
0 1
1 1
2 1
2 2
3 2
3 3
4 1
4 3
1 2
2 3
3 4

輸入說明：

就像圖表中說的那樣。

輸出格式：

第一行：一個整數，實際結果乘以1000後取整。請不要進行任何的4舍5入工作。

輸出樣例（file pwrfail.out）：

2828

【分析】 

很明顯，這是求圖的最短路徑問題，由於N=1000，顯然Floyd算法會超時，

所以要用SPFA、Dijkstra等 O(n^2)算法。

構圖時要用勾股定理算出任意兩點間的距離，因為有M的限制，

所以可以用鄰接表進行優化。

注意：C++中要用double型，因為這是實數。

【我的代碼】（用鄰接矩陣寫的，有空的話再改成鄰接表吧）

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
const double MAX=200000000;
const int MAXN=1001;
int N,W;
double M;
double Mat[MAXN][MAXN];
double dist[MAXN];
bool flag[MAXN];

class POING
{
public:
 int x,y;
}P[1001];

double GetDis(int a,int b)
{
 double tmp1,tmp2;
 tmp1=P[a].x-P[b].x;
 tmp2=P[a].y-P[b].y;
 double tmp=tmp1*tmp1+tmp2*tmp2;
 return sqrt(tmp);
}

void init()
{
 scanf("%d %d\n",&N,&W);
 scanf("%lf",&M);
 int a,b;
 for(int i=1;i<=N;i++)
  scanf("%d %d\n",&P[i].x,&P[i].y);
 
 for (int i=1;i<=N;i++)
 {
  for (int j=1;j<=N;j++)
  {
   Mat[i][j]=GetDis(i,j);
   if(Mat[i][j]>M)
    Mat[i][j]=MAX;
  }
 }
 
 for (int i=1;i<=W;i++)
 {
  scanf("%d %d\n",&a,&b);
  Mat[a][b]=0;
  Mat[b][a]=0;
 }
}

void Dijkstra(int S)
{
 for (int i=1;i<=N;i++)
 {
  dist[i]=Mat[S][i];
  flag[i]=false;
 }
 
 dist[S]=0;
 flag[S]=1;
 
 for (int i=2;i<=N;i++)
 {
  double tmp=MAX;
  int u=S;
  for (int j=1;j<=N;j++)
  {
   if(!flag[j] && dist[j]<tmp)
   {
    u=j;
    tmp=dist[j];
   }
  }
  flag[u]=1;
  
  for (int j=1; j<=N;j++)
  {
   if(!flag[j])
   {
    double newdist=dist[u]+Mat[u][j];
    if(newdist<dist[j])
    {
     dist[j]=newdist;
    }
   }
  }
 }
}

int main()
{
 freopen("pwrfail.in","r",stdin);
 freopen("pwrfail.out","w",stdout);
 init();
 Dijkstra(1);
 double tmp=dist[N];
 int ans;
 if(tmp==MAX)
  ans=-1;
 else
  ans=int(tmp*1000);
 printf("%d\n",ans);
 return 0;
} 

【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	5	0.000 s	8116 KB	0
2	正确	5	0.004 s	8116 KB	0
3	正确	5	0.007 s	8116 KB	0
4	正确	5	0.012 s	8116 KB	0
5	正确	5	0.021 s	8116 KB	0
6	正确	5	0.026 s	8116 KB	0
7	正确	5	0.036 s	8116 KB	0
8	正确	5	0.041 s	8116 KB	0
9	正确	5	0.058 s	8116 KB	0
10	正确	5	0.072 s	8116 KB	0
11	正确	5	0.070 s	8116 KB	0
12	正确	5	0.000 s	8116 KB	0
13	正确	5	0.072 s	8116 KB	0
14	正确	5	0.000 s	8116 KB	0
15	正确	5	0.000 s	8116 KB	0
16	正确	5	0.000 s	8116 KB	0
17	正确	5	0.001 s	8116 KB	0
18	正确	5	0.001 s	8116 KB	0
19	正确	5	0.001 s	8116 KB	0
20	正确	5	0.001 s	8116 KB	0

运行完成
运行时间 0.426 s
平均内存使用 8116 KB
测试点通过状况 AAAAAAAAAAAAAAAAAAAA
得分：100
恭喜你通过了全部测试点!