列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[sagit]

NPSC 2008 高中組 決賽 H.幼稚國王的行程

說明：給你一個有重覆邊的有向權重圖，請你找出可以在指定距離內回到自己的點。

解法：最短路徑的題目，逐點使用 Dijkstra's 的最短路徑演算法，看是不是能在指定距離內回到自己。這一題的測資有兩個陷阱，一是有的邊是自己回到自己，二是兩點之間可能不只有一個邊，要特別處理。

參考程式：(By sagit)

代碼: [選擇]

// NPSC 2008 高中組決賽
// 題目 H - 幼稚國王的行程
// By sagit at TCGS
#include <cstdlib>
#include <cstdio>

using namespace std;

const int MAX=1002, VERY_LONG=100000;
int G[MAX][MAX], D[MAX], V[MAX], Ans[MAX], An, Num, Dis;
// G 記錄兩點之間的距離, D 記錄到某點的最短距離, V 記錄該點是否已完成
// Ans 記錄答案, An 為答案個數, Num 為點的總數, Dis 為要求的距離

int main()
{
    freopen("ph.in", "rt", stdin);
    freopen("ph.out", "w+t", stdout);
    int k, m, i, j, a, b, c;
    scanf("%d", &k);
    while (k--)
    {
        scanf("%d%d%d", &Num, &m, &Dis);
        for (i=1; i<=Num; i++)          // 將所有點的距離設為很大
            for (j=1; j<=Num; j++)
                G[i][j]=VERY_LONG;
        for (i=0; i<m; i++)             // 輸入每個點的距離
        {
            scanf("%d%d%d", &a, &b, &c);
            if (a==b||G[a][b]<c) continue; // 連到自己或重覆而較長的邊不處理
            G[a][b]=c;
        }
        for (i=1, An=0; i<=Num; i++)    // 逐點做 Dijkstra
        {
            for (j=1; j<=Num; j++)      // 啟始化動作
                D[j]=G[i][j], V[j]=0;
            while (1)
            {
                for (j=1, a=0, b=VERY_LONG-1; j<=Num; j++) // 找一個最近的點
                    if (!V[j]&&D[j]<b) a=j, b=D[j];
                if (a==0||b>Dis) break; // 找不到就離開
                V[a]=1;
                for (j=1; j<=Num; j++)  // 以該點更新相鄰點的距離
                    if (!V[j]&&D[a]+G[a][j]<D[j]) D[j]=D[a]+G[a][j];
                if (D[i]<=Dis)          // 若回到原點在限定距離內, 則找到答案
                {
                    Ans[An++]=i;
                    break;
                }
            }
        }
        printf("%d\n", An);             // 列印答案
        for (i=0; i<An; i++)
        {
            if (i>0) printf(" ");
            printf("%d", Ans[i]);
        }
        printf("\n");
    }
//    system("PAUSE");
    return 0;
}

[sagit]

如果這一題的 N 改成最大為 500,
則也可以用 Floyd-Warshall 來解,
程式很容易寫,
而且答案也是正確的....

PS.本題測資以 Floyd-Warshall 來解,
時間約為 12 秒左右。

[lose]

這題用SPFA去解,速度更加快速

代碼: [選擇]

#include<stdlib.h>
#include<stdio.h>
#define MAX 1000000
short map[10001][500][2];
int min(int x,int y)
{
     if(x>=y) return y;
     else return x;
}
int input()   
{   
  char cha;   
  int x=0;   
  while(cha=getchar())   
     if(cha!=' '&&cha!='\n') break;   
  x=cha-48;   
  while(cha=getchar())   
    {   
     if(cha==' '||cha=='\n') break;   
      x=x*10+cha-48;   
    }   
    return x;   
}
short Queue[500000],maptop[1001]={0};
int SPFA(int S,int N,int L)
{
   int Dis[1001]={0},a,b,c,used[1001]={0};
   int top=-1;
   for(a=1;a<=N;a++)
      Dis[a]=MAX;
   for(a=0;a<maptop[S];a++)
     {
      Dis[map[S][a][0]]=min(Dis[map[S][a][0]],map[S][a][1]);
      if(used[map[S][a][0]]==0)
            Queue[++top]=map[S][a][0],used[map[S][a][0]]=1;
     }
   if(Dis[S]<=L) return 1;
   for(a=0;a<=top;a++)
      {
         int Qp=Queue[a];
         used[Qp]=0;
         if(Dis[Qp]>L) continue;
         for(b=0;b<maptop[Qp];b++)
            if(Dis[map[Qp][b][0]]>Dis[Qp]+map[Qp][b][1])
              {
                 Dis[map[Qp][b][0]]=Dis[Qp]+map[Qp][b][1];
                   if(used[map[Qp][b][0]]==0)
                      Queue[++top]=map[Qp][b][0],used[map[Qp][b][0]]=1;
              }
         if(Dis[S]<=L) return 1;
      }
   if(Dis[S]<=L) return 1;
   else return 0;
}
main()
{
  int k,N,M,Dis;
  scanf("%d",&k);
  while(k--)
     {
        scanf("%d %d %d",&N,&M,&Dis);
        int a,b,c,d,x,y;
        for(a=0;a<M;a++)
           {
            x=input(),y=input(),d=input();
              if(x==y) continue;
            map[x][maptop[x]][0]=y;
            map[x][maptop[x]++][1]=d;
           }
        int ANS[1001],top=0;
        for(a=1;a<=N;a++)
           {
              int Flag=SPFA(a,N,Dis);
              if(Flag==1) ANS[top++]=a;
           }
        printf("%d\n",top);
        for(a=0;a<top;a++)
          printf("%d ",ANS[a]);
        printf("\n");
        for(a=1;a<=N;a++)
           maptop[a]=0;
     }
  return 0;
}

[sagit]

感謝樓上的補充,
有興趣的人可以看看這兩篇文章：
http://dantvt.spaces.live.com/blog/cns!D87988A6CAC0A480!790.entry
http://dantvt.spaces.live.com/blog/cns!D87988A6CAC0A480!874.entry
討論三種最短路徑演算法的效率比較,
Dijkstra's還可以再加上Heap來優化,
在某些情況也不見得會輸SPFA,
所以還是看情況再決定要使用哪一種演算法,
如果是測資小的有向圖,
直接用Floyd-Warshall秒殺比較快....

[electron]

其實測過不管用 dijkstra or SPFA 都要加一點剪枝條件，也就是答到答案 <=L 就直接跳出
不需要再對這個點去做 relax 的動作，否則幾乎都會 TLE

[sagit]

嗯! 這也是為什麼Floyd-Warshall沒辦法過的原因,
因為它沒辦法做Cut....