POJ 3013 - SPFA..為毛通過率這麼低...

   題意抽象來說..就是給一個無向圖...要我們以結點1為根做一棵樹...使得代價最小...代價的定義是說每條邊乘以這條邊下面的子樹所有點之和...

   令pointi指為i點的權值...Li為線段的權值

   也就是說最後要求的是L1*(point2+point3+point..)+L2*(point2+point3+point..)+....這種式子的值最小...把這個式子化一下..可變成

   point2(L1+L2+...)+point3(L1+L2...)....

   為點的權值一開始就是确定的...是以題目就轉化成了求每個點到點1的距離之和要最小...

   因為題目是給的無向邊...是以構邊的時候要構一個正向一個反向...然後用Dijkstra 或者SPFA或者Bellman-Ford來求所有點到點1的最短路徑...然後再将每個d[ ] 乘以該點的權值再都加起來就是答案所求的最小代價..

    用Dijkstra效率低...必須要加Heap來優化才能在3000ms内過....Bellman-Ford也是效率低...而最好的方案還是SPFA...

    注意的是....題目雖然所給的輸入資料是不大于65536的...但最後的結果會很大...最好用 unsigned long long 來存儲...讀入和輸出用 %I64u..

    并且要注意判斷"No Answer"的情況..

Program:

#include<iostream>
#include<queue>
#define MAXN 50010
using namespace std;
struct pp
{
    int x,y,k,next;    
}line[MAXN*2];
int  n,m,i,T,link[MAXN];
unsigned long long w[MAXN],d[MAXN];
queue<int> myqueue;
void SPFA()
{
    int i,h,k;
    unsigned long long ans=0;
    bool used[MAXN],can[MAXN];
    memset(d,0x7F,sizeof(d));
    memset(can,false,sizeof(can));
    memset(used,false,sizeof(used)); 
    while (!myqueue.empty()) myqueue.pop();
    d[1]=0; myqueue.push(1); 
    while (!myqueue.empty())
    {
          h=myqueue.front();   myqueue.pop();
          used[h]=false;
          can[h]=true;
          k=link[h];
          while (k)
          {
                if (d[line[k].y]>d[h]+line[k].k)
                {
                    d[line[k].y]=d[h]+line[k].k;
                    if (!used[line[k].y])
                    {
                         myqueue.push(line[k].y); 
                         used[line[k].y]=true;                       
                    }                                    
                }
                k=line[k].next;
          }
    }  
    for (i=1;i<=n;i++)
    if (!can[i]) 
    {
         printf("No Answer\n");
         return;             
    }
    for (i=2;i<=n;i++) ans+=d[i]*w[i];
    printf("%I64u\n",ans);   
}
int main()
{ 
    scanf("%d",&T);
    while (T--)
    { 
        memset(link,0,sizeof(link)); 
        scanf("%d%d",&n,&m); 
        for (i=1;i<=n;i++) scanf("%I64u",&w[i]);
        i=m;  m=0;
        while (i--)
        {
            m++;  
            scanf("%d%d%d",&line[m].x,&line[m].y,&line[m].k);
            line[m].next=link[line[m].x]; link[line[m].x]=m;
            m++;  
            line[m].x=line[m-1].y; line[m].y=line[m-1].x; line[m].k=line[m-1].k;  
            line[m].next=link[line[m].x]; link[line[m].x]=m;
        }   
        SPFA();
    }
    return 0;   
}