冲刺NOIP2015提高组复赛模拟试题（五） 3.破坏基地

3.破坏基地

描述 Description

在Z国和W国之间一直战火不断。好不容易，W国的间谍把完整的Z国的军事基地的地图到手了。于是W国决定再次出击，一举击破Z国的防线。 W国认真研究了Z国的地形，发现Z国有N个军事基地，我们不妨编号成1..N，而且经过深刻研究，发现1号军事基地是资源补给基地，而N号军事基地是前线。由于地形的缘故，只有M对军事基地两两可达，当然是有距离的。此时W国的弹头紧缺，当下的弹头只能去毁灭一个军事基地。当然了，最重要的就是毁灭一个军事基地，使得资源补给基地与前线的最短距离发生变化。但是Z国也不是白痴，他们的资源补给基地与前线有着极高的防御力，所以W国只能去炸掉其余的N-2个基地，当然炸掉某个基地后，这个基地就不可达了。于是问题就来了，炸掉哪些基地后会使得资源补给基地与前线的最短距离发生变化呢？注：假若炸掉某个基地后，1号基地和N号基地不连通，那么我们也认为他们的最短距离发生了变化。

输入格式 InputFormat

输入数据第一行是两个正整数N，M，意义如题所述。接下来M行，每行包括三个正整数x，y，d，表示有一条边连接x、y两个地点，其距离为d。数据保证图是连通的。

输出格式 OutputFormat

输出数据的第一行包含一个整数K，表示有K个基地可毁灭，且毁灭其中任意一个后，资源补给基地与前线的最短距离发生变化。接下来K行，每行输出一个军事基地的编号，要求编号递增。在wyl8899神犇的率领下，W国必胜！！！因此一定不会存在K=0的情况。

样例输入 SampleInput [复制数据]

6 7

1 2 3

1 5 2

2 3 5

2 4 3

2 5 4

2 6 5

3 4 2

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

对于30%的数据，N<=100，M<=1,000；对于60%的数据，N<=2,000，M<=20,000；对于100%的数据，N<=10,000，M<=100,000，1<=d<=10,000；

时间限制 TimeLimitation

1s
解：spfa+记录前驱(输出路径)

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 #define sc(x) scanf("%d",&x)

 #define man 100010

 using namespace std;

 struct point

 {

     int next,to,cost;

     }e[man*];

 int n,num,m,head[man*],pre[man];

 int p[man],tot=;

 long long dis[man];

 bool vis[man];

 void add(int from,int to,int cost)

 {

     e[++num].next=head[from];

     e[num].to=to;

     e[num].cost=cost;

     head[from]=num;

     }

 queue<int>q;

 void spfa(int s)

 {

     for(int i=;i<=n;i++)

         dis[i]=;

     memset(vis,,sizeof(vis));

     q.push(s);

     dis[s]=;

     vis[s]=;

     while(!q.empty())

     {

         int u=q.front();

         q.pop();

         vis[u]=;

         for(int i=head[u];i;i=e[i].next)

         {

             int to=e[i].to;

             if(dis[to]>dis[u]+e[i].cost)

             {

                 dis[to]=dis[u]+e[i].cost;

                 pre[to]=u;

                 if(!vis[to])

                 {

                     vis[to]=;

                     q.push(to);

                     }

                 }

             }

         }

     }

 void print(int x)

 {

     if(pre[x]==x)

         return;

     print(pre[x]);

     p[++tot]=x;

     }

 int main()

 {   freopen("destroy.in","r",stdin);

     freopen("destroy.out","w",stdout);

     sc(n);sc(m);

     for(int x,y,z,i=;i<=m;i++)

     {

         sc(x);sc(y);sc(z);

         add(x,y,z);

         add(y,x,z);

         }

     spfa();

     pre[]=;

     print(n);

     sort(p+,p+tot+);

     printf("%d\n",tot-);

     for(int i=;i<=tot;i++)

     {   if(p[i]==||p[i]==n)

             continue;

         printf("%d\n",p[i]);}

     return ;

     }

巴特西

冲刺NOIP2015提高组复赛模拟试题（五） 3.破坏基地

最新文章

热门文章