P1144 最短路计数

提交 25.41k

通过 11.18k

时间限制 1.00s

内存限制 125.00MB

题目提供者洛谷

难度普及+/提高

历史分数100

提交记录

查看题解

题目描述

给出一个

输入格式

第一行包含

接下来

输出格式

共 $\bmod 100003ansmod100003后的结果即可。如果无法到达顶点iii则输出000。$

输入输出样例

输入 #1

输出 #1

思路

　　构建每个点所属的其最短路长度的组别，在跑Dijkstra的时候来更新当前点所属的组别，详见代码

ＣＯＤＥ

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 1e6 + 7;
 47 const int inf  = 0x3f3f3f3f;
 48 const int M = 100003;
 49 
 50 int head[maxn << 1], edge[maxn << 1], w[maxn << 1], nxt[maxn << 1];
 51 int cnt;
 52 
 53 inline void BuildGraph (int u, int v, int c) {
 54     cnt++;
 55     edge[cnt] = v;
 56     nxt[cnt]  = head[u];
 57     w[cnt] = c;
 58     head[u] = cnt;
 59 }
 60 
 61 struct node {
 62     int u,v;
 63     bool operator <(const node &t) const {
 64         return u > t.u;
 65     }
 66 };
 67 
 68 int n,m,s,t;
 69 int dis[maxn];
 70 int ans[maxn];
 71 priority_queue < node > q;
 72 
 73 void dijkstra(int s) {
 74     for (int i = 1; i <= n; ++i) {
 75         dis[i] = inf;
 76     }
 77     dis[s] = 0;
 78     node temp;
 79     temp.u = 0;
 80     temp.v = s;
 81     q.push(temp);
 82     while(!q.empty()) {
 83         int u = q.top().v;
 84         int d = q.top().u;
 85         q.pop();
 86         if(d != dis[u]) continue;
 87         for (int i = head[u]; i; i = nxt[i]) {
 88             int v = edge[i];
 89             int c = w[i];
 90             if(dis[v] > dis[u] + c) {
 91                 dis[v] = dis[u] + c;
 92                 node p;
 93                 p.u = dis[v], p.v = v;
 94                 ans[v] = ans[u];///把当前点加入这条最短路长度的行列
 95                 q.push(p);
 96             }
 97             else if(dis[v] == dis[u] + c) {
 98                 //printf("ans[%d]:%d\n",u,ans[u]);
 99                 //printf("ans[%d]:%d\n",v,ans[v]);
100                 ans[v] += ans[u];///当前点加上其他当前长度的行列
101                 ans[v] %= M;
102                 //printf("ans[%d]:%d\n",u,ans[u]);
103                 //printf("ans[%d]:%d\n\n",v,ans[v]);
104             }
105         }
106     }
107 }
108 
109 int main()
110 {
111     scanf("%d %d",&n, &m);
112     int a, b;
113     for (int i = 1; i <= m; ++i) {
114         scanf("%d %d",&a, &b);
115         BuildGraph(a, b, 1);
116         BuildGraph(b, a, 1);
117     }
118     ans[1] = 1;
119     dijkstra(1);
120     for ( int i = 1; i <= n; ++i ) {
121         printf("%d\n",ans[i]);
122     }
123     return 0;
124 }