百度之星 初赛三 最短路 2 Dijkstra
2024-09-05 07:16:46
打比赛的时候切的,不过竟然 wa 了 14 次~
挺简单的,直接在跑 $Dijkstra$ 的时候记录一下路径最大值就好了.
#include <bits/stdc++.h>
#define inf 100000000000000
#define ll long long
#define mod 998244353
#define N 1003
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,m,s;
struct Node
{
int u;
ll dis;
Node(int u=0,ll dis=0):u(u),dis(dis){}
bool operator<(Node b)const
{
return b.dis<dis;
}
};
priority_queue<Node>q;
int hd[N],nex[N<<2],pre[N<<2],edges,done[N],to[N<<2],now[N<<2];
ll f[N][N],d[N];
ll val[N<<2];
inline void addedge(int u,int v,ll c)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;
}
inline void Dijkstra()
{
int i,u,v;
for(i=1;i<=n;++i) done[i]=0;
for(i=0;i<=n;++i) d[i]=inf,pre[i]=0,now[i]=i;
d[s]=0, q.push(Node(s,0)), pre[s]=0,now[s]=0;
while(!q.empty())
{
Node e=q.top(); u=e.u,q.pop();
if(done[u]) continue;
done[u]=1;
if(u!=s)
{
now[u]=max(u, pre[u]);
}
for(i=hd[u];i;i=nex[i]){
if(d[to[i]]>=d[u]+val[i]){
if(d[to[i]]>d[u]+val[i])
{
d[to[i]]=d[u]+val[i];
pre[to[i]]=now[u];
q.push(Node(to[i],d[to[i]]));
}
else {
if(now[u]<pre[to[i]]) pre[to[i]]=now[u];
}
}
}
}
}
int main() {
setIO("input");
using namespace IO;
int T;
scanf("%d",&T);
while(T--) {
int i,j;
scanf("%d%d",&n,&m);
edges=0;
for(i=1;i<=n;++i) hd[i]=0;
for(i=1;i<=n;++i) for(j=1;j<=n;++j) f[i][j]=inf;
for(i=1;i<=n;++i) f[i][i]=0;
for(i=1;i<=m;++i) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,(ll)c), addedge(b,a,(ll)c), f[a][b]=f[b][a]=min(f[a][b],(ll)c);
}
int ans=0;
for(i=1;i<=n;++i) {
s=i, Dijkstra();
for(j=1;j<=n;++j)
ans=(long long) (ans+pre[j])%mod;
}
printf("%d\n",ans); }
return 0;
}
最新文章
- 使用webstorm+webpack构建简单入门级“HelloWorld”的应用&;&;引用jquery来实现alert
- Thinking in Unity3D
- WebService中使用Aspose.Cells.dll
- settings.php rwx
- AngularJS作出简单聊天机器人
- Clank – 快速构建移动 APP 原型的 HTML/CSS 框架
- Awesomplete - 零依赖的简单自动完成插件
- COGS731 [网络流24题] 最长递增子序列(最大流)
- javaZIP压缩文件
- Unity3D - 关于Dynamic和Static
- 【原】模式之-适配器Adapter模式
- SomeThing of Memcache
- HDU4099(斐波那契数列与字典树)
- 深入浅出—JAVA(3)
- Libgdx Box2D现实------这缓释微丸(一个:项目介绍)
- 关于Java、Python、Go编程思想的不同
- Spring Data JPA,一种动态条件查询的写法
- 机器翻译评测——BLEU改进后的NIST算法
- CentOS7 查看操作系统版本信息
- nexus的安装和简介(3)