P1144 最短路计数
提交29.99k
通过13.03k
时间限制1.00s
内存限制125.00MB
题目描述
给出一个N个顶点M条边的无向无权图，顶点编号为1?N。问从顶点1开始，到其他每个点的最短路有几条。
输入格式
第一行包含22个正整数N,M，为图的顶点数与边数。
接下来M行，每行2个正整数x,y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。
输出格式
共NN行，每行一个非负整数，第ii行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出an*smod100003后的结果即可。如果无法到达顶点i则输出0。
输入输出样例
输入 #1复制
5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5
输出 #1复制
1 1 1 2 4
说明/提示
1到5的最短路有4条，分别为2条1?2?4?5和2条1?3?4?5（由于4?5的边有2条）。
对于20%的数据，N≤100；
对于60%的数据，N≤1000；
对于100%的数据，N<=1000000,M<=2000000。
思路：可以理解成最短路，边的权重都为1，到达某点的距离最短。那么如何计算距离最短的路径有多少条呢?我们可以整一个num数组存放当前结点的路径条数，如果到达下一个点的路径更新了，那么到下一个点的路径条数应该为当前结点的路径条数，如果下一个结点的路径与他原来的距离相等，则加上去当前结点的路径。
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int maxn = 1e6 + 100;
const int MAX = 1e8;
const int mod = 100003;
struct node{int to;int next;int weight;
}edge[2 * maxn];int head[maxn];
int dist[maxn];
int num[maxn];
bool vis[maxn];
int cnt = 0;
int n, m;void init()
{for(int i = 1; i <= n; i++){head[i] = -1;vis[i] = false;dist[i] = MAX;num[i] = 0;}
}void add(int u, int v)
{edge[cnt].to = v;edge[cnt].weight = 1;edge[cnt].next = head[u];head[u] = cnt++;
}struct base{int point, dist;bool operator < (const base&others)const{return dist > others.dist;}
};void dijkstra(int s)
{priority_queue<base>q;dist[s] = 0;num[s] = 1;//源点的路径条数为1q.push((base){s, 0});while(!q.empty()){base cur = q.top();q.pop();int u = cur.point;if(vis[u])continue;vis[u] = true;for(int i = head[u]; ~i; i = edge[i].next){int v = edge[i].to;int w = edge[i].weight;if(!vis[v] && dist[u] + w <= dist[v]){if(dist[u] + w < dist[v]){//dist小，则更新路径条数num[v] = num[u];dist[v] = dist[u] + w;q.push((base){v, dist[v]});//这里错了}else{//相等，则加上路径条数num[v] += num[u];}num[v] %= mod;}}}}int main()
{scanf("%d%d", &n, &m);init();while(m--){int u, v;scanf("%d%d", &u, &v);add(u, v);add(v, u);}dijkstra(1);for(int i = 1; i <= n; i++){printf("%d\n", num[i] % mod);}return 0;
}