Main » 2013 October 8 » ["扫地"杯III day1]破坏基地
12:52 PM ["扫地"杯III day1]破坏基地 |
最短路加判断用数组模拟链表写的，速度很快#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<vector> #include<set> #include<map> #include<string> #include<algorithm> #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) #define pb push_back #define mp make_pair #define N 200100 #define L 400100 using namespace std; typedef long long LL; typedef long double LD; int len=0,n,m; int pre[N],last[N],w[N],e[N],q[L],dis[N],inq[N],path[N]; bool f[N],candel[N]; void add(int x,int y,int z) { pre[++len]=last[x]; last[x]=len; e[len]=y;w[len]=z; } void check(int &x) {if (x==L) x=1;} void SPFA(int v0) { int i,h=0,t=1; FOR(i,1,n) dis[i]=2e9; dis[v0]=0; inq[v0]=1; q[1]=v0; while (h!=t) { h++;check(h); int u=q[h]; int p=last[u]; while (p) { int W=w[p],v=e[p]; if (dis[u]+W<dis[v]) { dis[v]=dis[u]+W; path[v]=u; if (!inq[v]) { t++;check(t); q[t]=v; inq[v]=1; } } p=pre[p]; } inq[u]=0; } } int main() { ios::sync_with_stdio(false); scanf("%d %d",&n,&m); int x,y,z; int i; FOR(i,1,m) { scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } SPFA(1); int t=n; memset(f,0,sizeof(f)); memset(candel,0,sizeof(candel)); while (t) { f[t]=1; candel[t]=1; t=path[t]; } FOR(i,2,n-1) { int p=last[i]; while (p) { int j=e[p]; if (f[j]) { int W=w[p]; if (dis[i]+W==dis[j]) if (i!=path[j]) { candel[pre[j]]=1; } } p=pre[p]; } } candel[1]=0; candel[n]=0; int cnt=0; FOR(i,1,n) if (candel[i]) cnt++; printf("%d\n",cnt); FOR(i,1,n) if (candel[i]) printf("%d\n",i); return 0; } |
|
|
| Total comments: 0 | |