[多源最短路]USACO 奶牛聚會 spart

譯: zqzas

N(1 ≤ N ≤ 1000)個農場中的每個農場都有一隻奶牛去參加位於第X個農場的聚會.共有M (1 ≤ M ≤ 100,000)條單向的道路,每條道路連接一對農場.通過道路i會花費Ti (1 ≤ Ti ≤ 100)的時間.

作爲參加聚會的奶牛必須走到聚會的所在地(農場X).當聚會結束時,還要返回各自的農場.奶牛都是很懶的,她們想找出花費時間最少的路線.由於道路都是單向的,所有她們前往農場X的路線可能會不同於返程的路線.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back? 對於所有參加聚會的奶牛,找出前往聚會和返程花費總時間最多的奶牛,輸出這隻奶牛花費的總時間.

 

輸入格式:

• 第1行:三個用空格隔開的整數.

第2行到第M+1行,每行三個用空格隔開的整數:Ai, Bi,以及Ti.表示一條道路的起點,終點和需要花費的時間.

輸出格式:

• 唯一一行:一個整數: 所有參加聚會的奶牛中,需要花費總時間的最大值.

样例输出:

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

样例输入:

10

样例说明:
共有4只奶牛參加聚會,有8條路,聚會位於第2個農場.

第4只奶牛可以直接到聚會所在地(花費3時間),然後返程路線經過第1和第3個農場(花費7時間),總共10時間.

【分析】

裸SPFA………我沒寫優化，結果10組一共0.3秒～

我一同學，Floyd也過了！！！！

http://paulinsider.at.ua/news/sparty/2011-11-07-7

【我的代碼】

裸代碼RawCode

C++语言: Codee#25525

001 /*
002 *Problem: USACO sparty
003 *Author: Yee-fan Zhu
004 *Email: zyfworks@gmail.com
005 *Method: SPFA
006 */
007 #include <cstdio>
008 #include <cstdlib>
009 #include <vector>
010 #include <queue>
011 #define min(a,b) (a>b?b:a)
012 using namespace std;
013 const int MAXN=1001;
014 const int INF=100000;
015 typedef vector<int>Vec;
016 Vec Map[MAXN];
017 Vec Val[MAXN];
018 int Mat[MAXN][MAXN];
019
020 int N,M,X;
021
022 void init()
023 {
024     scanf("%d %d %d\n",&N,&M,&X);
025     for(int i=1;i<=N;i++)
026         for(int j=1;j<=N;j++)
027             Mat[i][j]=INF;
028     int s,e,v;   
029     for(int i=1;i<=M;i++)
030     {
031         scanf("%d %d %d\n",&s,&e,&v);
032         Mat[s][e]=min(Mat[s][e],v);
033     }       
034     for(int i=1;i<=N;i++)
035     {
036         for(int j=1;j<=N;j++)
037         {
038             if(Mat[i][j]==INF)
039                 continue;
040             Map[i].push_back(j);
041             Val[i].push_back(Mat[i][j]);
042         }
043     }
044 }
045
046 queue<int> Q;
047 unsigned short int dist[MAXN];
048 unsigned short int flag[MAXN];
049 int spfa(int S,int E)
050 {
051     for(int i=1;i<=N;i++)
052         dist[i]=INF,flag[i]=0;
053     dist[S]=0;
054     flag[S]=1;
055     Q.push(S);
056     int tmp,nxt,ndist;
057     while(!Q.empty())
058     {
059         tmp=Q.front();
060         Q.pop();
061         flag[tmp]=0;
062         for(unsigned int i=0;i<Map[tmp].size();i++)
063         {
064             ndist=dist[tmp]+Val[tmp][i];
065             nxt=Map[tmp][i];
066             if(ndist<dist[nxt])
067             {
068                 dist[nxt]=ndist;
069                 if(!flag[nxt])
070                 {
071                     Q.push(nxt);
072                     flag[nxt]=1;
073                 }
074             }
075         }
076     }
077     return dist[E];
078 }
079
080 void solve()
081 {
082     int sp1,sp2,sp;
083     int Max=0;
084     for(int i=1;i<=N;i++)
085     {
086         if(i==X)
087             continue;
088         sp1=spfa(i,X);
089         sp2=spfa(X,i);
090         sp=sp1+sp2;
091         if(sp>Max)
092             Max=sp;
093     }
094     printf("%d\n",Max);
095     //printf("%d\n",clock());
096 }
097
098 int main()
099 {
100     freopen("sparty.in","r",stdin);
101     freopen("sparty.out","w",stdout);
102     init();
103     solve();
104     return 0;
105 }