愚者指名自己的辩护人_纪中2046_最短路_维包一生推，gosick大法好!

输入

第一行两个整数 N,M，表示点数和边数。
接下来一行 N 个整数，第 i 个正整数表示 Pi。
接下来 M 行，每行两个整数 u,v，表示有一条无向边连接了 u 和 v。

输出

输出 N 行，每行为一个 0 或 1，意义如题目描述所示。

题解

枚举去掉哪些点会对结果产生影响，就是必定经过的点
精度是个问题需要注意
spfa是最快的，复杂度$O(nmk)$
floyd是最简单的，复杂度$O(n^{4})$
这里两种都有打，floyd开O2快得飞起但仍然没有spfa快
维包一生推，gosick大法好!!!

Code

floyd

#include <stdio.h>
#include <cmath>
using namespace std;
double f[101][101],t[101][101];
int p[101],r[101],n,m;
__attribute__((optimize("O2")))
inline double max(double x,double y)
{return x<y?y:x;
}
__attribute__((optimize("O2")))
inline void init()
{for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)f[i][j]=t[i][j];
}
__attribute__((optimize("O2")))
inline void floyd(int v)
{for (int k=1;k<=n;k++)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (i!=j&&i!=k&&j!=k&&i!=v&&j!=v&&k!=v)f[i][j]=max(f[i][k]*f[k][j]/100.0,f[i][j]);
}
int main()
{freopen("fool.in","r",stdin);freopen("fool.out","w",stdout);scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%d",&p[i]);p[i]=100-p[i];}for (int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);f[x][y]=t[x][y]=p[y];f[y][x]=t[y][x]=p[x];}floyd(0);double ans=f[1][n];r[1]=1;r[n]=1;for (int v=2;v<n;v++){init();floyd(v);if (abs(ans-f[1][n])>0.000001||!f[1][n])r[v]=1;}for (int i=1;i<=n;i++)printf("%d\n",r[i]);return 0;
}

spfa

#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
struct edge
{int y;double w;int next;
}e[401];
int ls[401],r[101],p[101],n,m,maxE=0;
double d[101];
bool vis[101];
__attribute__((optimize("O2")))
inline void add(int x,int y,double w)
{e[++maxE]=(edge){y,w,ls[x]};ls[x]=maxE;
}
__attribute__((optimize("O2")))
inline double spfa(int v)
{queue<int>q;memset(d,0,sizeof(d));memset(vis,false,sizeof(false));q.push(1);d[1]=p[1];while (!q.empty()){int now=q.front();q.pop();for (int i=ls[now];i;i=e[i].next)if (e[i].y!=v&&e[i].w*d[now]/100.0>d[e[i].y]){d[e[i].y]=e[i].w*d[now]/100.0;if (!vis[e[i].y]){vis[e[i].y]=true;q.push(e[i].y);}}vis[now]=false;}return d[n];
}
int main()
{freopen("fool.in","r",stdin);freopen("fool.out","w",stdout);scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%d",&p[i]);p[i]=100-p[i];}for (int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);add(x,y,p[y]);add(y,x,p[x]);}double ans=spfa(0);printf("1\n");for (int i=2;i<n;i++){double tmp=spfa(i);if (abs(tmp-ans)>0.0000001||abs(tmp-0)<=0.0000001)printf("1\n");elseprintf("0\n");}printf("1\n");return 0;
}