NOIAC52 | 计算机

Portal

计算机将重复上述过程,直到稳定

题中改写值的操作相当于最短路中对最短路长度的更新。每个节点上的值可以看作是从 1 号点到其它点的最短路的长度,而每个边的编号可以看作是该边的权。对于正常的 Dijkstra 当 d[u]+w<d[v] 时才进行更新 ,而对于该题,只要将更新的条件改为 max(d[u],w)<d[v] 即可。考试的时候居然没想出来,被自己菜哭。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
typedef std::pair<int,int> node;
const int inf=1e9,_=1e5+1,__=3e5+1;
int n,m,fp=1,d[_],hed[_],ver[__<<1],edg[__<<1],nxt[__<<1];
namespace IO {
char buf[32];int len=0;
int read() {
int x=0;char c=getchar();
while(c<48||c>57) c=getchar();
while(c>47&&c<58) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x;
}
void write(int x) {
while(x) buf[++len]=x%10,x/=10;
for(;len;--len) putchar(buf[len]+48);putchar('\n');
}
}
void link(int u,int v,int w) {
ver[++fp]=v;edg[fp]=w;nxt[fp]=hed[u];hed[u]=fp;
ver[++fp]=u;edg[fp]=w;nxt[fp]=hed[v];hed[v]=fp;
}
void dijkstra() {
std::fill(d,d+_+1,inf);d[1]=0;int u,v,w,vis[_];
memset(vis,0,sizeof(vis));
std::priority_queue<node> beap;beap.push((node){0,1});
while(beap.size()) {
u=beap.top().second;beap.pop();if(vis[u]) continue;vis[u]=1;
for(int i=hed[u];i;i=nxt[i]) {
v=ver[i],w=std::max(d[u],edg[i]);
if(d[v]>w) d[v]=w,beap.push((node){-d[v],v});
}
}
}
int main() {
n=IO::read(),m=IO::read();
for(int i=1;i<=m;++i) link(IO::read(),IO::read(),i);
dijkstra();puts("0");
for(int i=2;i<=n;++i) IO::write(d[i]);
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。