hgfs @ 2024-07-18 10:15:35
第46行的cout,我用来检查,删掉以后答案就不对,但不删的话答案是正确的!
#include<bits/stdc++.h>
using namespace std;
int const N=5003,M=200003;
int g[N][N],dis[N],n,m,su;
bool st[N];
int find(){
int an,in=0x3f3f3f3f;
for(int i=1;i<=n;i++){
if(dis[i]<in && !st[i]){
in=dis[i];
an=i;
}
}
st[an]++;
return an;
}
/*-------法二
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1 || dis[j]<dis[t]))
t=j;
}
st[t]=1;
*/
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof(g));
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
if(x==y) continue;
g[x][y]=min(g[x][y],z);//防止重边。
g[y][x]=min(g[y][x],z);
}
dis[1]=0;//编号1的点距离为0.
for(int i=1;i<=n;i++){
int x=find();
for(int j=1;j<=n;j++) dis[j]=min(dis[j],min(g[j][x],g[x][j]));//枚举其他边。
cout<<x<<' '<<dis[x]<<endl;
if(i!=1 && dis[x]==0x3f3f3f3f){
cout<<"orz";//无法到达,
return 0;
}
su+=dis[x];
}
cout<<su;
return 0;
}
/*
5 6
1 2 3
2 3 4
3 1 4
4 5 6
5 4 6
1 3 5
*/
那一行代码加上,就输出orz,不加就输出15.
by Kavin_0409 @ 2024-07-18 10:27:46
6
by Kavin_0409 @ 2024-07-18 10:28:16
确实奇葩
by nr0728 @ 2024-07-18 10:31:36
@hgfs 你把 cout 改成 cerr 试试
上次就有道题我代码有 ub,加上 cout 就对了,然后把 cout 改成 cerr,不开 O2 交就能 A
by nr0728 @ 2024-07-18 10:32:57
@hgfs 你代码不是 CE 了吗,是不是直接执行编译好的源文件没注意到 CE
/tmp/compiler_2dz3pkft/src:16:14: 错误:use of an operand of type ‘bool’ in ‘operator++’ is forbidden in C++17
by hgfs @ 2024-07-18 11:07:49
@nr0728 感谢感谢!关了o2就过了。
好像没有CE呀~~
by zhaoyonghao @ 2024-08-01 08:14:35
我喜欢链式前向星
#include <bits/stdc++.h>
using namespace std;
int m, n, head[5005], cnt, dis[5005];
bool vis[5005];
struct node{
int to, w, next;
}edge[400005];
void add(int u, int v, int w)
{
edge[++cnt] = {v, w, head[u]};
head[u] = cnt;
}
int main()
{
memset(head, -1, sizeof head);
memset(dis, 0x3f, sizeof dis);
cin >> m >> n;
for (int i = 1; i <= n; i++)
{
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dis[1] = 0;
int ans = 0;
for (int i = 1; i <= m; i++)
{
int x = 0;
for (int j = 1; j <= m; j++)
if (dis[j] < dis[x] && vis[j] == 0) x = j;
ans += dis[x];
vis[x] = 1;
for (int j = head[x]; j != -1; j = edge[j].next)
if (vis[edge[j].to] == 0) dis[edge[j].to] = min(dis[edge[j].to], edge[j].w);
}
for (int i = 1; i <= m; i++)
if (!vis[i])
{
cout << "orz\n";
return 0;
}
cout << ans << "\n";
return 0;
}