Description
小明經(jīng)常去N 個地點，其中有些地點之間有直接的無向道路（共M 條這樣的道路），可以直接互相到達(dá)，這些道路的長短不一。由于小明對這些道路都很熟悉，無論起點和終點在哪里，總能走最短路。小明有嚴(yán)重的強(qiáng)迫癥，認(rèn)為奇數(shù)很不和諧，如果他某一天從一個地點去另一個地點走過的路程是奇數(shù)，就會很不爽，但他又不想白白多走路，所以遇到最短路長度是奇數(shù)的情況就只能忍了。
如果從某個地點A 到另一個地點B 的最短路徑長度為奇數(shù)，則稱這條最短路徑為“不和諧最短路”。如果一條不和諧最短路上包含地點C，則稱它為“經(jīng)過C 的不和諧最短路”。現(xiàn)在請你編程求出對于每個地點，經(jīng)過它的不同的不和諧最短路數(shù)量。兩條最短路不同，當(dāng)且僅當(dāng)它們途徑的地點的序列不同。

Input
第一行兩個正整數(shù)N;M，含義見題面。
接下來M 行，每行三個正整數(shù)Ai;Bi;Li，表示一條無向道路的兩端和長度。

Output
　N 行每行一個整數(shù)，第i 行表示經(jīng)過第i 個點的不同的不和諧最短路條數(shù)。

Sample Input
4 4
1 4 1
1 2 1
3 4 100
2 3 2

Sample Output
6
4
2
2
樣例說明
長度為奇數(shù)的最短路有:1 → 2; 1 → 2 → 3; 1 → 4; 2 → 1; 3 → 2 → 1; 4 → 1。
這些路徑中四個點的經(jīng)過次數(shù)分別為6, 4, 2, 2。
其它一些路，如1 → 4 → 3 不是最短路，2 → 3 是最短路但長度為2，是偶數(shù)。這些路都不計入答案。

Data Constraint
對于50% 的數(shù)據(jù)，N ≤ 100；
對于全部數(shù)據(jù)，N ≤ 1000;M ≤ 3000，每條路的長度不超過1000。
保證圖連通，無自環(huán)重邊。

.
.
.
.
.
分析
題目中的圖是一般圖，結(jié)構(gòu)復(fù)雜沒有規(guī)律。考慮枚舉起點并計算單源最短路，保留所有最短路中的邊（有向），原圖就變成了一個 DAG，可以很方便地在上面進(jìn)行拓?fù)渑判?#xff0c;DP 等。再考慮長度為奇數(shù)的最短路，從一個點斷開，一定是一邊長度為奇數(shù)，另一邊長度為偶數(shù)。因此可以在 DAG 上 DP 計算從起點到達(dá)每個點的奇偶最短路徑分別有幾條，再逆序 DP 計算從每個點出發(fā)的奇偶最短路徑條數(shù)，在后面的 DP 過程中順便統(tǒng)計答案。這樣對每個起點算一遍。
復(fù)雜度 O(NM log N)。

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;int ans[2000],d[2000],head[2000],pre[2000],n,m,cnt=1; bool f[2000]; queue<int>q;struct node { int to,next,w; }edge[10000];void add(int x,int y,int z) { edge[cnt].next=head[x];edge[cnt].to=y;edge[cnt].w=z;head[x]=cnt++; }void dfs(int x,int y) {if (d[x]%2!=0){for (int j=x;j;j=pre[j]) ans[j]++;}for (int i=head[x];i;i=edge[i].next){if (y+edge[i].w==d[edge[i].to]){pre[edge[i].to]=x;dfs(edge[i].to,y+edge[i].w);pre[edge[i].to]=0;}} }void spfa(int x) {memset(d,0X7f,sizeof(d));q.push(x);d[x]=false;while (!q.empty()){int u=q.front();f[u]=0;for (int i=head[u];i;i=edge[i].next){if (d[u]+edge[i].w<d[edge[i].to]){d[edge[i].to]=d[u]+edge[i].w;if (f[edge[i].to]==false){q.push(edge[i].to);f[edge[i].to]=true;} }}q.pop();}dfs(x,0); }int main() {scanf("%d%d",&n,&m);for (int i=1;i<=m;i++) {int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}for (int i=1;i<=n;i++) spfa(i);for (int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/10458932.html

總結(jié)

以上是生活随笔為你收集整理的【五校联考6day2】san的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。