Rhizomys

Rhizomys

描述

竹鼠养殖场有若干个小房间，有很多条双向道路连接着它们。

值得注意的是，在养殖场中，连接两个房间的道路可能不止一条。由于路上能看到的风景不同，我们认为这两条路是不同的。

同时，也可能存在一条道路是从一个房间出发又回到它自身，但我们规定，从一个房间到它自己的最短距离为 0。

为了不被吃掉，竹鼠们决定开始运动，运动的方式是从一个小房间经过若干个小房间（中间经过的房间数可以为 0）走到另一个小房间。

但竹鼠们也希望在锻炼过程中尽可能地偷懒，这意味着，竹鼠运动的路线总是沿最短路的。

现在，竹鼠们希望知道从 1 号房间分别到其他所有房间的运动路线的种数。由于它们害怕会因为写代码而被吃掉，所以它们找到了你帮忙。

输入

第一行是两个整数 N,MN,M，表示房间个数和连接房间的道路的条数。

接下来 mm 行，每行三个整数 u,v,cu,v,c，表示 uu 号房间与 vv 号房间之间存在一条长度为 cc 的双向道路。

输

输出 NN 行，第 ii 行表示从 11 号房间到 ii 号房间的运动路径的种数，由于答案可能会很大，你只需要输出它模 911814911814 的结果。

当不存在任何一条从 11 号房间到i 号房间的道路时，请输出 00。

输入样例 1

输样例 1

样例 1 解释

以下用 EiEi 表示输入中的第 ii 条边。到 1 的最短路长度为 0，只有 1 条。

到 2 的最短路长度为 2，有 2 条（ E1E1 ， E10E10 ）。到 3 的最短路长度为 3，只有 1 条（ E3E3 -> E5E5 ）。到 4 的最短路长度为 4，有 3 条

（ E3E3 -> E7E7 ， E1E1 -> E2E2 ， E10E10 -> E2E2 ）。

到 5 的最短路长度为 1，只有 1 条（ E9E9 ）。到 6 的最短路长度为 2，只有 1 条（ E3E3 ）。

输入样例 2

点此下载。

限制

对于 20%的数据，1≤n≤100,1≤m≤20001≤n≤100,1≤m≤2000；

对于 50%的数据，1≤n≤1000,1≤m≤1500001≤n≤1000,1≤m≤150000； 对于 100%的数据，

1≤n≤20000,1≤m≤500000,1≤u,v≤n,1≤c≤101≤n≤20000,1≤m≤500000,1≤u,v≤n

,1≤c≤10。

提示

[这道题统计最短路的数目，我们不妨考虑将所有处在最短路上的边提出来]

[提出这些边后形成了原图的一张子图，显然这张子图是不会有环的，否则与最短路的定义矛盾]

[既然没有环，那我们就可以愉快地做动态规划啦~]

[请同学们思考，如果使用 dijkstra 算法，需要先求最短路，再拓扑排序吗？]

代码

#include <iostream> #include<vector> #include<queue> #include<vector> #include<stack> #include<string.h>

#pragma warning(disable:4996) using namespace std;

// ================= 代码实现开始 =================

int Dist[20000];

long long State[20000]; bool   outQ[20000]; const int mo = 911814;

/* 请在这里定义你需要的全局变量 */ struct QMember

{

int node;

int Dist;

int friend operator > (QMember s1, QMember s2) {

return s1.Dist > s2.Dist;

}

};

struct Edge

{

Edge *next=nullptr;//该点所拥有的下一条边

int go=0;//该点所指向的节点号

int cost;//边的权值

};

Edge *Head[20000]; QMember Node[20000];

priority_queue<QMember,vector<QMember>,greater<QMember>> Q;

// 给定n个点m条边的无向图，求1到其余每个点的最短路的数目

// n：如题意

// m：如题意

// U：大小为m的数组，表示m条无向边中的一个端点

// V：大小为m的数组，表示m条无向边中的另一个端点

// C：大小为m的数组，表示m条无向边的长度

void getAnswer(int n, int m, vector<int> U, vector<int>V, vector<int>C) {

/* 请在这里设计你的算法 */

memset(Dist, 999999, sizeof(Dist));

//初始化点的序号

for (int i = 0; i < n+1; i++)

{

Head[i] = new Edge();

Node[i].node = i;

}

//处理相邻的点及其边

int i = 0;

while (i<m)

{

int u = U[i];

int v = V[i];

int c = C[i];

if (u == v)

{

i++;

continue;

}

//若u或v为1，说明此时应该将相邻点压入Q中以循环

if (u == 1)

{

if (Dist[v] == c)

State[v]++;

else if (Dist[v] > c)

{

Dist[v] = c;

State[v] = 1;

Node[v].Dist = c;

Q.push(Node[v]);

}

}

if (v == 1)

{

if (Dist[u] == c)

State[u]++;

else if (Dist[u] > c)

{

Dist[u] = c;

State[u] = 1;

Node[u].Dist = c;

Q.push(Node[u]);

}

}

if(Head[u]->go==0)//若Head[u]->go==0说明v是u的第一条边所指向的节点

{

Head[u]->go = v;

Head[u]->cost = c;

}

else

{

Edge *ed = new Edge();

ed->go = v;

ed->cost = c;

ed->next = Head[u]->next;

Head[u]->next = ed;

}

if (Head[v]->go == 0)//若Head[u]->go==0说明v是u的第一条边所指向的节点

{

Head[v]->go = u;

Head[v]->cost = c;

}

else

{

Edge *ed = new Edge();

ed->go = u;

ed->cost = c;

ed->next = Head[v]->next;

Head[v]->next = ed;

}

i++;

}

outQ[1] = true;

Dist[1] = 0;

State[1] = 1;

while (!Q.empty())

{

//Qtop:堆顶元素

QMember QTop = Q.top();

Q.pop();

//curNode:当前堆顶的点

//curDist:1->curNode的最短长度

//curState:1->curNode的最短数目

int curNode = QTop.node, curDist = Dist[curNode], curState = State[curNode];

//如果curNode已经用于更新过，则跳过;否则打上出队标记

if (outQ[curNode])

continue;

else

outQ[curNode] = true;

//枚举每一条与curNode相连的边

//Head[curEdge]为curNode的第一条边

for (Edge *curEdge = Head[curNode]; curEdge != nullptr; curEdge = curEdge->next)

{

//nextNode:当前与curNode相连的边的另一个端点

int nextNode = curEdge->go;

//如果从1沿最短路到curNode，再到nextNode的路与原来的方案长度相同时

//以下if中的内容暂定，可能会有错误

if (Dist[nextNode] == curDist + curEdge->cost)

{

State[nextNode] += State[curNode];

if (State[nextNode] > mo)

State[nextNode] % mo;

}

else if (Dist[nextNode] > curDist + curEdge->cost)

{

Dist[nextNode] = curDist + curEdge->cost;

State[nextNode] = State[curNode];

Node[nextNode].Dist = Dist[nextNode];

Q.push(Node[nextNode]);//由于更新了新的最短路径，故原先nextNode所到其

他点的距离也需要更新

}

}

}

for (int i = 1; i <= n; i++)

{

printf("%d\n", State[i]);

}

return;

}

// ================= 代码实现结束 =================

int main() {

int n, m;

scanf("%d%d", &n, &m);

vector<int> U, V, C;

for (int i = 0; i < m; ++i) {

int u, v, c;

scanf("%d%d%d", &u, &v, &c);

U.push_back(u);

V.push_back(v);

C.push_back(c);

}

getAnswer(n, m, U, V, C);

return 0;

}