[最短路徑]USACO Silver09 找工作 jobhunt 解題報告

問題描述:
貝茜牛身無分文了，她正忙着找工作。農夫約翰知道這個情況，他想讓他的牛去周遊世界，於是他推行了一個規則：在他的牛到另 一個城市工作之前，她們只能在一個城市掙得 D （ 1 <= D <= 1,000 ）美元。不管怎樣，貝茜可以在別的城市工作過之後，再返回到某個城市，並在這個城市再掙 D 美元，她可以無限次數地這樣做。
貝茜牛的世界包括 P （ 1 <= P <= 150 ）條單向邊，這些邊連接着 C （ 2 <= C <= 220 ）個城市，城市按 1 到 C 的順序編號，貝茜牛目前正待在 S 城 (1 <= S <= C) 。單向邊 i 從城市 A_i 連到城市 B_i ，其中 1 <= A_i <= C; 1 <= B_i <= C ，在路上不花費任何代價。
爲了幫助貝茜，約翰授權它使用他的私人噴氣飛機服務。這項服務配置了 F 條航綫，每條航綫是由城市 J_i 到城市 K_i (1 <=J_i <= C; 1 <= K_i <= C) 的單向航綫，且在該航綫上的費用是 T_i( 1 <= T_i <= 50,000 ) 美元，如果貝茜牛手頭沒有現錢，它可以將來掙到錢之後再支付飛行費用。
只要它願意，貝茜可以隨時隨地選擇退出。不限時間，假定它所有去過的城市都能掙足 D 美元，最後貝茜最多能得到多少錢？如果這個數目沒有限制的話輸出 -1 。
程序名：jobhunt
輸入格式：
第1行：五個空格隔開的整數，D，P，C，F，S；
第2至P+1行：第i行包括兩個空格隔開的整數，表示從城市A_i到B_i有一條單向邊。
第P+2至P+F+1行：第P+i行包括三個空格隔開的整數，表示從城市J_i到T_i有一條單向航綫，費用是T_i。
輸入樣例：(jobhunt.in):
100 3 5 2 1
1 5
2 3
1 4
5 2 150
2 5 120
輸入樣例解釋：這個世界有5個城市，三條有向邊，和兩條飛行航綫，貝茜從城市1開始，在每個城市它能最多掙到100美元。
輸出格式：
只有一行，一個整數，表示在遵守規則的情況下，它最多能得到多少錢。
輸出樣例：(jobhunt.out):
250
輸出樣例解釋：貝茜能從城市1→城市5→城市2→城市3，最後共得到4*100 - 150 = 250美元。
「分析」
單源最短路問題，賺錢是負權，航費是正權，用SPFA處理負邊權即可。
「我的代碼」

#include "cstdio"
#include "iostream"
#include "cstdlib"
#include "queue"
using namespace std;
const int MAX=230;
int Map[MAX][MAX];
int dist[MAX];
int times[MAX];
bool flag[MAX];
const int MAXN=1000000000;
int D;//在每個城市最多掙得D美金
int P;//P條單向邊
int C;//C個城市
int F;//F個單項航線
int S;//源點
typedef queue QUEUE;
void init()
{
 scanf("%d %d %d %d %d\n",&D,&P,&C,&F,&S);
 for (int i=1;i<=C;i++)
  for (int j=1;j<=C;j++)
   Map[i][j]=MAXN;
 for (int i=1;i<=C;i++)
  Map[i][i]=0;
 for (int i=1;i<=P;i++)
 {
  int a,b;
  scanf("%d %d\n",&a,&b);
  Map[a][b]=-D;
 }
 for (int i=1;i<=F;i++)
 {
  int a,b,c;
  scanf("%d %d %d\n",&a,&b,&c);
  if(Map[a][b]==MAXN)
  {
   Map[a][b]=c-D;
  }
 }
 return;
}
QUEUE Q;
void SPFA()
{
 for (int i=1;i<=C;i++)
  dist[i]=MAXN,flag[i]=false,times[i]=0;
 dist[S]=-D;
 Q.push(S);
 int x;
 while(Q.size())
 {
  x=Q.front();
  Q.pop();
  flag[x]=false;
  for(int i=1;i<=C;i++)
  {
   int tmp=dist[x]+Map[x][i];
   if(tmpC)
     {
      printf("-1\n");
      return;
     }
    }
   }
  }
 }
 int Max=MAXN;
 for (int i=1;i<=C;i++)
  if(Max>dist[i])
   Max=dist[i];
 printf("%d\n",-Max);
 return;
}
int main()
{
 freopen("jobhunt.in","r",stdin);
 freopen("jobhunt.out","w",stdout);
 init();
 SPFA();
 return 0;
}