codeforcesRound#241(div2)E解题报告

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 

题目大意:

给出一个图,要求求出每个点之间的最短距离的路总条数.

解法:

由于需要求出每个点之间的最短距离的路总条数,我们可以将问题拆分为: 1.最短距离; 2.符合最短距离的路的总条数.

对于问题1,可以用floyd算法可以算出来;

对于问题2,本题的重点所在,要求出路的总条数,而且不能重复.不能重复的话,我们可以按照每个点来计算,且每个点,我们只计算点周围的最短路径的路的条数,这样就可以防止重复. 因为1条边不可能统计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节点的路总条数加一

		//由于是最短路,不存在可以重复的边,例如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点,则可以说明,需要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();
}