暴力大法好
首先Floyd算出所有城市都没有问题的最短路存进dis
再枚举每一个出问题的城市，暴力判断即可
没有重要的城市记得输出"No important cities."！！！
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
int read() {
int x=1,ans=0;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')
x*=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
ans=ans*10+ch-48;
ch=getchar();
}
return x*ans;
}
int edge[205][205],dis[205][205],n,m,temp[205][205];
int main() {
n=read();m=read();
memset(edge,0x3f,sizeof(edge));
for(int i=1;i<=m;i++) {
int u=read(),v=read(),val=read();
edge[u][v]=edge[v][u]=val;
}
memcpy(dis,edge,sizeof(edge));
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
for(int wow=1;wow<=n;wow++) {
memcpy(temp,edge,sizeof(temp));
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(k!=wow)
temp[i][j]=min(temp[i][j],temp[i][k]+temp[k][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((i!=wow)&&(j!=wow)&&(temp[i][j]>dis[i][j])&&(i!=j)) {
printf("%d ",wow);
// cout<<i<<' '<<j<<' '<<temp[i][j]<<' '<<dis[i][j]<<endl;
i=n+1;j=n+1;
}
}
return 0;
}
复杂度n^4,可是简单的暴力只有80分
我们用一个三维数组ycl[k]表示先算出前k个城市作为中点所算到一般的最短路状态，枚举的时候zhijei调用即可
这样复杂度可以降到(n^4)/2
勉强水过
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
int read() {
int x=1,ans=0;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')
x*=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
ans=ans*10+ch-48;
ch=getchar();
}
return x*ans;
}
int edge[205][205],dis[205][205],n,m,temp[205][205],ycl[205][205][205];
bool ok=true;
int main() {
n=read();m=read();
memset(edge,0x3f,sizeof(edge));
for(int i=1;i<=m;i++) {
int u=read(),v=read(),val=read();
edge[u][v]=edge[v][u]=val;
}
memcpy(dis,edge,sizeof(edge));
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
memcpy(ycl[0],edge,sizeof(edge));
for(int k=1;k<=n;k++) {
memcpy(ycl[k],ycl[k-1],sizeof(ycl[k-1]));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ycl[k][i][j]=min(ycl[k][i][j],ycl[k][i][k]+ycl[k][k][j]);
}
for(int wow=1;wow<=n;wow++) {
memcpy(temp,ycl[wow-1],sizeof(ycl[wow-1]));
for(int k=wow+1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(k!=wow)
temp[i][j]=min(temp[i][j],temp[i][k]+temp[k][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((i!=wow)&&(j!=wow)&&(temp[i][j]>dis[i][j])&&(i!=j)) {
printf("%d ",wow);
ok=false;
i=n+1;j=n+1;
}
}
if(ok) puts("No important cities.");
return 0;
}
