#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 2147483647
using namespace std;
//描述：一个地方有F个farm，分别为f1,f2,...,fp.
//其中，f1是谷仓！有几只tmd的肥牛站在这些fram上，它们闲着没事干就想着去
//偷吃谷子，可惜，在它们吃到谷子之前M秒，有个摄像头把它们的位置拍下来了
//！fi与fj之间有路径连通，并且知道走这条路径的时间t。我们还知道总共有C
//只牛，它们各自站在不同或者相同的farm上！


//这题是我做过的最复杂的dijkstra,只要把关系理清，其实也不难
//解题思路：首先a数组是用来存地图的
//dist很有学问，他不仅要放最短路径长，还要放这个点上的牛的编号，可能有多个牛，故定义成一个结构体 
// 它包含一个长度d和一个容器
//在初始化过程中要特别初始化对角线，还有对之前的case要把v清空 
//输入边时考虑重边取最小的
//接下来就是dijkstra了，最后线性扫描dist，把距离小于m的找出来
//如果它的v非空，则把他所含的牛的编号放入新的容器vv中
//对它排序输出 
struct NODE
{
    int d; 
    vector<int> v;//这个是用来放牛的编号的，因为同一个地方可能有好机头牛   
    }dist[501];
bool s[501];
int a[501][501];
int main()
{
    int n,i,j,k,min,temp,f,p,c,m,x,y,len;//f是农场个数，p是边数，c牛的个数,m是时限 
    while(cin>>f>>p>>c>>m)
    {
          for(i=1;i<=f;i++)//初始化 
          {
              for(j=1;j<=f;j++)
              {
                  a[i][j]=MAX;             
                  }
              a[i][i]=0; 
              (dist[i].v).clear();//对之前case进行处理                
              }                
          for(i=1;i<=p;i++)//输入边，注意有重边选最小的那条 
          {
              cin>>x>>y>>len;
              if(a[x][y]>len)
              {
                 a[x][y]=len;
                 a[y][x]=len;              
                 }             
              } 
          for(i=1;i<=c;i++)
          {
              cin>>n;
              (dist[n].v).push_back(i);             
              }
              
          for(i=1;i<=f;i++)
          {
              dist[i].d=a[1][i];
              s[i]=0;             
              }      
          s[1]=1;
          for(i=1;i<f;i++)
          {
              min=MAX;
              j=1;
              for(k=2;k<=f;k++)
              {
                  if(!s[k]&&dist[k].d<min)
                  {
                     min=dist[k].d;
                     j=k;                     
                     }               
                  }      
              s[j]=1;
              for(k=2;k<=f;k++)
              {
                  if(!s[k]&&a[j][k]<MAX)
                  {
                     temp=dist[j].d+a[j][k];
                     if(temp<dist[k].d)
                     {
                        dist[k].d=temp;
                        //               
                        }                     
                     }             
                  }          
              }         
          vector<int>vv;
          for(i=1;i<=f;i++)
          {
//              cout<<"dist["<<i<<"].d="<<dist[i].d<<endl;
//              system("pause");
              if(dist[i].d<=m)//可疑对象的条件成立 
              {
                 if(!(dist[i].v).empty())//这地方有牛!
                 {                                  
                    for(j=0;j<(dist[i].v).size();j++)//这个地方所有的牛都放进容器里 
                    {
                        vv.push_back((dist[i].v)[j]);                             
                        }
                    }            
                 }             
              }
          sort(vv.begin(),vv.end());//对牛编号排序，按升序输出 
          cout<<vv.size()<<endl; 
          for(i=0;i<vv.size();i++)
          {
              cout<<vv[i]<<endl;                    
              }        
          }
    return 0;
    }
//写的不好还请见谅^__^

• Re:写份解题报告，只是菜鸟，大牛别见笑 (56) 306457592 2011-01-03 22:43:43