手机浏览微网站,wordpress外汇,电影网站建设视频教程,做淘客网站哪个cms好最短路计数
题目描述
给出一个 N N N 个顶点 M M M 条边的无向无权图#xff0c;顶点编号为 1 ∼ N 1\sim N 1∼N。问从顶点 1 1 1 开始#xff0c;到其他每个点的最短路有几条。
输入格式
第一行包含 2 2 2 个正整数 N , M N,M N,M#xff0c;为图的顶点数与边数…最短路计数
题目描述
给出一个 N N N 个顶点 M M M 条边的无向无权图顶点编号为 1 ∼ N 1\sim N 1∼N。问从顶点 1 1 1 开始到其他每个点的最短路有几条。
输入格式
第一行包含 2 2 2 个正整数 N , M N,M N,M为图的顶点数与边数。
接下来 M M M 行每行 2 2 2 个正整数 x , y x,y x,y表示有一条由顶点 x x x 连向顶点 y y y 的边请注意可能有自环与重边。
输出格式
共 N N N 行每行一个非负整数第 i i i 行输出从顶点 1 1 1 到顶点 i i i 有多少条不同的最短路由于答案有可能会很大你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 i i i 则输出 0 0 0。
样例 #1
样例输入 #1
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5样例输出 #1
1
1
1
2
4提示 1 1 1 到 5 5 5 的最短路有 4 4 4 条分别为 2 2 2 条 1 → 2 → 4 → 5 1\to 2\to 4\to 5 1→2→4→5 和 2 2 2 条 1 → 3 → 4 → 5 1\to 3\to 4\to 5 1→3→4→5由于 4 → 5 4\to 5 4→5 的边有 2 2 2 条。
对于 20 % 20\% 20% 的数据 1 ≤ N ≤ 100 1\le N \le 100 1≤N≤100 对于 60 % 60\% 60% 的数据 1 ≤ N ≤ 1 0 3 1\le N \le 10^3 1≤N≤103 对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 1 0 6 1\le N\le10^6 1≤N≤106 1 ≤ M ≤ 2 × 1 0 6 1\le M\le 2\times 10^6 1≤M≤2×106。
#includebits/stdc.h
using namespace std;
#define il inline
const int MAXN2e65;
const int MOD100003;
int n,m;
int dis[MAXN],cnt[MAXN];
bool vis[MAXN];
queueint q;
vectorint nextpoints[MAXN];//bfs
il void bfs()
{memset(dis,0x3f3f,sizeof(dis));//初始化dis[1]0;cnt[1]1;vis[1]1;q.push(1);while(!q.empty())//广搜{int xq.front();q.pop();for(auto y:nextpoints[x]){if(!vis[y]){if(dis[x]1dis[y]){dis[y]dis[x]1;vis[y]true;q.push(y);}//打标记存更优}if(dis[x]1dis[y]){cnt[y]cnt[x];cnt[y]%MOD;}} }return;
}
// int main()
{cinnm;for(int i1;im;i){int u,v;cinuv;nextpoints[u].push_back(v);nextpoints[v].push_back(u);}bfs();for(int i1;in;i)coutcnt[i]endl;//输出答案return 0;
} ps:
单源最短路问题 1.可以bfs的同时用cnt记录1~i的最短路径条数 2.假设存在一条 → 的边。 若 d i s i 1 d i s j 就令 d i s j d i s i 1 c n t j c n t i 若dis_i1dis_j就令dis_jdis_i1cnt_jcnt_i 若disi1disj就令disjdisi1cntjcnti 若 d i s i 1 d i s j 就令 c n t j c n t i 若dis_i1dis_j就令cnt_jcnt_i 若disi1disj就令cntjcnti
