Description

Crossbell 自治州有著四通八達的現代化交通。時值獨立慶典之際，隨著來自周邊國家旅客的日益增
多，犯罪行為也悄無聲息開始滋長起來。
特別任務支援科的警察們從總部收到了關于調查偽裝在游客中的犯罪分子的請求。通過調查，他們
得到了一張地圖，記載了 Crossbell 自治州內每一條道路的長度。
顯然，為了減少犯罪行為被發現的可能性，犯罪分子總是會選擇最短的路徑來行動。為了方便安排
人手和推測犯罪分子采取的路線，他們希望得知任意兩個地點之間，有多少條犯罪分子可能會選擇的道
路。

Input

第一行，包含兩個整數N;M，表示Crossbell 內的地點數和道路數。
接下來N 行，每行包含三個整數xi; yi; li，表示道路連接的兩個不同地點的標號，以及道路的長度。
道路是雙向的。
兩個不同地點之間不會有超過一條道路。

Output

輸出一行，包含N(N -11)/2 個整數C1,2;C1,3; : : : ;C1,N ;C2,3;C2,4; : : : ;C2,N ; : : : ;CN-1,N。
其中Cx,y 表示x 號地點到y 號地點之間有多少條犯罪分子可能會選擇的道路。

Sample Input

5 6
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
4 5 4

Sample Output

1 4 1 2 1 5 6 1 2 1

Data Constraint

? 對于分值為30 的子任務1，保證 N<=50
? 對于分值為30 的子任務2，保證 N<=100
? 對于分值為40 的子任務3，保證 N<=500。

Solution

• 這題解法顯然，5秒鐘的時限保證了不會卡常！

• 首先枚舉枚舉每一個點作為源點，對于這個點做一次SPFA（單源最短路）

• 同時記錄每個點到源點的最短路徑，這樣是 O(N2) 的

• 之后枚舉按題目要求的每一個源點之外的點，往回走

• 中途標記每條走過的邊，這樣還是 O(N2) 的

• 所以加上第一層的枚舉，總的時間復雜度是 O(N3) 的，成功碾過~

Code

#include<cstdio> #include<cstring> #define clr(a,b) memset(a,b,sizeof(a)) using namespace std; const int N=501; int n,m,x,y,z,ans; int b[N][N]; int que[3*N],f[N],g[N][N]; int bz[N],p[N]; inline void spfa(int x) {int l=f[que[1]=x]=0,r=1;while(l<r){int k=que[++l];bz[k]=false;for(int i=1;i<=n;i++)if(b[k][i]!=b[0][0])if(f[k]+b[k][i]<f[i]){f[i]=f[k]+b[k][i];g[i][g[i][0]=1]=k;if(!bz[i]) bz[que[++r]=i]=true;}elseif(f[k]+b[k][i]==f[i]) g[i][++g[i][0]]=k;} } inline void dfs(int x,int y) {p[x]=true;for(int i=1;i<=g[x][0];i++){int k=g[x][i];ans++;if(k!=y && !p[k]) dfs(k,x);} } int main() {scanf("%d%d",&n,&m);clr(b,43);for(int i=1,x,y,z;i<=m;i++){scanf("%d%d%d",&x,&y,&z);b[x][y]=b[y][x]=z;}for(int i=1;i<n;i++){clr(f,43),clr(g,0);spfa(i); for(int j=i+1;j<=n;j++){clr(p,ans=0);dfs(j,0);printf("%d ",ans);}}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 3808. 【NOIP2014模拟8.25】道路值守的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。