算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

这道题先跑一遍最短路，然后考虑到所有最短路径形成的图是有向无环图，可以DP。
然后，dis值按照小到大顺序进行遍历。

C++ 代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define pii pair <int, int>
using namespace std;
const int mod = 2147483647;
const int maxn = 1000 + 5;
bool vis[maxn];
vector <int> G[maxn], W[maxn];
int n, m, dis[maxn], cnt[maxn], order[maxn];
struct cmp
{
    inline bool operator () (const int &x, const int& y)
    {
        return dis[x] < dis[y];
    }
};
void Dijkstra()
{
    priority_queue <pii> Q;
    while(!Q.empty()) Q.pop();
    memset(vis, false, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    Q.push(make_pair(dis[1], 1));
    while(!Q.empty())
    {
        int u = Q.top().second; Q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = 0; i < G[u].size(); ++ i)
        {
            int v = G[u][i], w = W[u][i];
            if(dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                Q.push(make_pair(-dis[v], v));
            }
        }
    }
    return;
}
void Prim()
{
    for(int i = 0; i < n; ++ i) order[i] = i + 1;
    sort(order, order + n, cmp());
    memset(cnt, 0, sizeof(cnt));
    int u;
    for(int i = 0; i < n; ++ i)
    {
        u = order[i];
        if(cnt[u] == 0) cnt[u] = 1;//最短路后，整张图变为一张拓扑图 
        for(int i = 0; i < G[u].size(); ++ i)
        {
            int v = G[u][i], w = W[u][i];
            if(dis[v] == dis[u] + w) ++ cnt[v];
        }
    }
    return;
}
int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++ i) G[i].clear(), W[i].clear();

    for(int i = 0; i < m; ++ i)
    {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        G[x].push_back(y), G[y].push_back(x);
        W[x].push_back(z), W[y].push_back(z);
    }
    Dijkstra();
    Prim();
    int ans = 1;
    for(int i = 1; i <= n; ++ i) ans = (long long) ans * cnt[i] % mod;
    printf("%d\n", ans);
    return 0;
}