POJ_2394_最短路径---SPFA算法

//============================================================================

// Name        : POJ_2394.cpp

// Author      : tiger

// Version     :

// Copyright   : Your copyright notice

// Description : 最短路径---SPFA算法

//============================================================================

#include <iostream>

#include <cstdio>

#include <queue>

using namespace std;

const int MAXN = 501;

const int inf = 100000000;

int mat[MAXN][MAXN];

bool v[MAXN];

int dist[MAXN];

void spfa(int s,int n)

{

 queue<int> q;

 q.push(s);

 v[s] = true;

 dist[s] = 0;

 int t,i;

 while (!q.empty())

 {

  t = q.front();

  q.pop();

  v[t] = false;

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

  {

   if (dist[t] + mat[t][i] < dist[i])

   {

    dist[i] = dist[t] + mat[t][i];

    if (!v[i])

    {

     v[i] = true;

     q.push(i);

    }

   }

  }

 }

}

int main()

{

 freopen("in", "r", stdin);

 int F, P, C, M;

 int i, j, k, sum, a, b;

 int cows[101];

 scanf("%d %d %d %d", &F, &P, &C, &M);

 for (i = 0; i < F; i++)

 {

  for (j = 0; j < F; j++)

   mat[i][j] = inf;

  mat[i][i] = 0;

  v[i] = false;

  dist[i] = inf;

 }

 for (i = 0; i < P; i++)

 {

  scanf("%d %d %d", &a, &b, &k);

  a--;

  b--;

  if (k < mat[a][b])

  {

   mat[a][b] = k;

   mat[b][a] = k;

  }

 }

 spfa(0,F);

 sum = 0;

 for(i = 0; i < C; i++)

 {

  scanf("%d",cows + i);

  if(dist[cows[i]-1] <= M )

   {

    sum++;

    cows[i] = 1;

   }

  else

   cows[i] = 0;

 }

 printf("%d/n",sum);

 for(i = 0; i < C; i++)

 {

  if(cows[i])

   printf("%d/n",i+1);

 }

 return 0;

}