E. President's Path time limit per test 4 seconds memory limit per test 256 megabytes input standard input output standard output Good old Berland has n cities and m roads. Each road connects a pair of distinct cities and is bidirectional.

E. President's Path

time limit per test

memory limit per test

input

output

Good old Berland has n cities and m roads. Each road connects a pair of distinct cities and is bidirectional. Between any pair of cities, there is at most one road. For each road, we know its length.

We also know that the President will soon ride along the Berland roads from city s to city t. Naturally, he will choose one of the shortest paths from s to t, but nobody can say for sure which path he will choose.

The Minister for Transport is really afraid that the President might get upset by the state of the roads in the country. That is the reason he is planning to repair the roads in the possible President's path.

Making the budget for such an event is not an easy task. For all possible distinct pairs s,?t (s?t) find the number of roads that lie on at least one shortest path from s to t.

Input

The first line of the input contains integers n,?m (2?≤?n?≤?500, 0?≤?m?≤?n·(n?-?1)?/?2) — the number of cities and roads, correspondingly. Then m lines follow, containing the road descriptions, one description per line. Each description contains three integersxi,?yi,?li (1?≤?xi,?yi?≤?n,?xi?≠?yi,?1?≤?li?≤?106), where xi,?yi are the numbers of the cities connected by the i-th road and li is its length.

Output

Print the sequence of integers c12,?c13,?...,?c1n,?c23,?c24,?...,?c2n,?...,?cn?-?1,?n, where cst is the number of roads that can lie on the shortest path from s to t. Print the elements of sequence c in the described order. If the pair of cities s and t don't have a path between them, then cst?=?0.

Sample test(s)

input

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

output

1 4 1 2 1 5 6 1 2 1 

題目大意:

給出一個圖,要求求出每個點之間的最短距離的路總條數(shù).

解法:

由于需要求出每個點之間的最短距離的路總條數(shù),我們可以將問題拆分為: 1.最短距離; 2.符合最短距離的路的總條數(shù).

對于問題1,可以用floyd算法可以算出來;

對于問題2,本題的重點所在,要求出路的總條數(shù),而且不能重復(fù).不能重復(fù)的話,我們可以按照每個點來計算,且每個點,我們只計算點周圍的最短路徑的路的條數(shù),這樣就可以防止重復(fù). 因為1條邊不可能統(tǒng)計2次.(詳見代碼).

代碼:

#include 
#include 
#include 
#include 

using namespace std;

const int lim = 500000001;

class TMain {
 
 private:
 
 int n, m, f[505][505], dis[505][505], ans[505][505], now[505];
 
 public:
 
 int run() {
 scanf("%d %d", &n, &m);
 for (int i = 1; i <= n; i++)
 for (int j = 1; j <= n; j++)
 if (i == j)
 f[i][j] = dis[i][j] = 0;
 else
 f[i][j] = dis[i][j] = lim;
 for (int i = 1; i <= m; i++) {
 int a, b, c;
 scanf("%d %d %d", &a, &b, &c);
 dis[a][b] = dis[b][a] = f[a][b] = f[b][a] = min(f[a][b], c);
 }
 
 for (int k = 1; k <= n; k++)
 for (int i = 1; i <= n; i++)
 for (int j = 1; j <= n; j++)
 f[i][j] = min(f[i][j], f[i][k] + f[k][j]); //算出每對點之間的最短路徑

 for (int i = 1; i <= n; i++) { //從
 for (int j = 1; j <= n; j++) now[j] = 0;

 for (int j = 1; j <= n; j++)
 for (int k = 1; k <= n; k++)
 if (j != k && f[i][j] + dis[j][k] == f[i][k]) //逐一判斷與k點鏈接的邊是否在最短路徑上
 now[k]++; //若在,則k節(jié)點的路總條數(shù)加一

	//由于是最短路,不存在可以重復(fù)的邊,例如f[i][j]是一條邊, now[i]和now[j]只能在兩者之間的某一個累加
 for (int j = 1; j <= n; j++)
 for (int k = 1; k <= n; k++)
 if (f[i][j] + f[j][k] == f[i][k]) //如若最短路徑需要經(jīng)過j點,則可以說明,需要j點的最短路徑
 ans[i][k] += now[j]; //累加起來
 }
 
 for (int i = 1; i < n; i++)
 for (int j = i + 1; j <= n; j++)
 if (f[i][j] == lim)
 printf("0 ");
 else
 printf("%d ", ans[i][j]);
 printf("\n");
 return 0;
 }
}Main;

int main()
{
 return Main.run();
}

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com