传送门
分析
用dijkstra跑一遍最短路，在这个过程中，转移一下就可以得到答案了 如果当前点
v
v
v满足
d
i
s
[
v
]
=
=
d
i
s
[
u
]
+
w
[
e
]
dis[v]==dis[u]+w[e]
dis[v]==dis[u]+w[e] 那么
a
n
s
[
v
]
=
a
n
s
[
u
]
+
a
n
s
[
v
]
ans[v]=ans[u]+ans[v]
ans[v]=ans[u]+ans[v]，相当于原来有
a
n
s
[
v
]
ans[v]
ans[v]条到 v 的最短路，现在又可以通过 u ，那么个数自然相加
如果满足
d
i
s
[
v
]
>
d
i
s
[
u
]
+
w
[
e
]
dis[v]>dis[u]+w[e]
dis[v]>dis[u]+w[e] 说明到 v 的最短路条数就是到 u 的 容易得到
a
n
s
[
v
]
=
a
n
s
[
v
]
ans[v]=ans[v]
ans[v]=ans[v]
注意初始化
a
n
s
[
S
]
=
1
ans[S]=1
ans[S]=1（S为起点） 这道题还需要注意一下重复给边的情况，去重并且保存最短的那一条 由于洛谷数据比较水，直接边搞边加边也不会TLE 但ldw老师的OJ就比较厉害了，只有最后再 n2 跑一遍建图，防止多建，才不会TLE
惊奇的发现自己的dijkstra+堆优化的板子居然是错的…………………… 好吧，其实也不算是错 就是复杂度有点高，是（n+m）log n 的 因为我没有开 vis 数组，就反复地再松弛 平时都没有计数，所以没有发现问题 今天用之前的板子来计数，就明显发现会多记很多 还好，phew~，发现得不晚
代码
#include<bits/stdc++.h>
#define in read()
#define N 2004
#define M 4000009
#define re register
using namespace std
;
inline int read(){
char ch
;int f
=1,res
=0;
while((ch
=getchar())<'0'||ch
>'9') if(ch
=='-') f
=-1;
while(ch
>='0'&&ch
<='9'){
res
=(res
<<3)+(res
<<1)+ch
-'0';
ch
=getchar();
}
return f
==1?res
:-res
;
}
int head
[N
],to
[M
],nxt
[M
],w
[M
],cnt
=0;
inline void add(int x
,int y
,int z
){
nxt
[++cnt
]=head
[x
];head
[x
]=cnt
;to
[cnt
]=y
;w
[cnt
]=z
;
}
int g
[N
][N
],d
[N
],ans
[N
],n
,m
,vis
[N
];
priority_queue
<pair
<int ,int> > q
;
inline void dij(){
memset(d
,127/3,sizeof(d
));
q
.push(make_pair(0,1));d
[1]=0;ans
[1]=1;
while(!q
.empty()){
int u
=q
.top().second
;q
.pop();
if(vis
[u
]) continue;
vis
[u
]=1;
for(int re e
=head
[u
];e
;e
=nxt
[e
]){
int v
=to
[e
];
if(d
[v
]>d
[u
]+w
[e
]){
d
[v
]=d
[u
]+w
[e
];
ans
[v
]=ans
[u
];
q
.push(make_pair(-d
[v
],v
));
}
else if(d
[v
]==d
[u
]+w
[e
]) ans
[v
]+=ans
[u
];
}
}
}
int main(){
n
=in
;m
=in
;
memset(g
,127/3,sizeof(g
));
int inf
=g
[0][0];
for(int re i
=1;i
<=m
;++i
){
int u
=in
,v
=in
,dis
=in
;
if(dis
>=g
[u
][v
]) continue;
g
[u
][v
]=dis
;
}
for(int i
=1;i
<=n
;++i
)
for(int j
=1;j
<=n
;++j
)
if(g
[i
][j
]!=inf
)
add(i
,j
,g
[i
][j
]);
dij();
if(d
[n
]==inf
) cout
<<"No answer";
else cout
<<d
[n
]<<' '<<ans
[n
];
return 0;
}
