P3905 道路重建
我一开始想错了，我的是类似kruskal，把毁坏的边从小到大加，并且判断联通性。但是这有一个问题，你可能会多加，就是这条边没用，但是它比较小，你也加上了。
居然还有10分，数据也是水水的。。。
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstring>
#define inf 2147483647
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar()
//by war
//2017.10.10
using namespace std;
int n,m,dd,A,B,x,y,v,t;
int a[][];
bool b[][];
int d[];
int ans; struct node
{
int l,r,v;
bool operator<(const node&aa)const
{
return v<aa.v;
}
}e[]; void in(int &x)
{
char c=g();x=;
while(c<''||c>'')c=g();
while(c<=''&&c>='')x=x*+c-'',c=g();
}
void o(int x)
{
if(x>)o(x/);
p(x%+'');
} int find(int x)
{
if(d[x]==x)return x;
d[x]=find(d[x]);
return d[x];
} int main()
{
in(n),in(m);
For(i,,n)
d[i]=i;
For(i,,m)
{
in(x),in(y),in(v);
a[x][y]=v;
a[y][x]=v;
}
in(dd);
For(i,,dd)
{
in(x),in(y);
b[x][y]=true;
b[y][x]=true;
}
in(A),in(B);
For(i,,n)
For(j,,n)
{
if(!b[i][j]&&a[i][j]>)
d[find(i)]=find(j);
if(b[i][j])
{
e[++t].l=i;
e[t].r=j;
e[t].v=a[i][j];
}
}
sort(e+,e+t+);
For(i,,t)
{
if(find(A)!=find(B))
{
if(find(e[i].l)!=find(e[i].r))
{
d[find(e[i].l)]=find(e[i].r);
ans+=e[i].v;
}
}
else
{
o(ans);
break;
}
}
return ;
}
正解是把未坏的边的权值设成0，坏的边的值不变，跑spfa即可。
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstring>
#define inf 2147483647
#define len 10010
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar() using namespace std;
int n,m,x,y,v,dd,A,B;
queue<int>q;
int d[];
bool vis[],b[][]; struct node
{
int n,v;
node *next;
}*e[len]; void push(int x,int y,int v)
{
node *p;
p=new node();
p->n=y;
p->v=v;
if(e[x]==NULL)
e[x]=p;
else
{
p->next=e[x]->next;
e[x]->next=p;
}
} void in(int &x)
{
int y=;
char c=g();x=;
while(c<''||c>'')
{
if(c=='-')
y=-;
c=g();
}
while(c<=''&&c>='')x=x*+c-'',c=g();
x*=y;
} void o(int x)
{
if(x<)
{
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
} void spfa(int x)
{
For(i,,n)
d[i]=inf;
d[x]=;
q.push(x);
node *p;
int t;
while(q.size()>)
{
t=q.front();
p=e[t];
vis[t]=true;
while(p!=NULL)
{
if(!b[t][p->n])
{
if(d[t]<d[p->n])
{
d[p->n]=d[t];
if(!vis[p->n])
q.push(p->n);
}
}
else
{
if(d[t]+p->v<d[p->n])
{
d[p->n]=d[t]+p->v;
if(!vis[p->n])
q.push(p->n);
}
}
p=p->next;
}
vis[t]=false;
q.pop();
}
} int main()
{
in(n),in(m);
For(i,,m)
{
in(x),in(y),in(v);
push(x,y,v);
push(y,x,v);
}
in(dd);
For(i,,dd)
{
in(x),in(y);
b[x][y]=true;
b[y][x]=true;
}
in(A),in(B);
spfa(A);
o(d[B]),p(' ');
return ;
}