ZCMU—1200

1200: 小明的难题

Time Limit: 1 Sec  Memory Limit: 128 MB

[​​Submit​​​][​​Status​​​][​​Web Board​​]

Description

这是一个小明认为很难的问题，快到五一长假了，小明突然想去旅游，但是他有一些想去的地方，他搜集了他想去的地方的路线信息，但是他搜集的信息太多了，因此他决定把制定路线的事情交给你（他的大管家）。为了描述方便，我们将他可能要经过的n个城市编号1,2,…, n,当然他要求他到目的地所需的时间最短。

Input

一共有t组数据，每组数据的第一行有两个正整数n, m,(n<=1000,m<=10000)分别表示城市的数量和路的条数，接下来m行，每行有三个整数a,b,c,(1=<a,b<=n ,0<c<100), 分别表示城市a和 城市b之间有一条路要花c的时间，最后一行的两个整数s,e，代表小明的起始点和目的地。

Output

输出一路上要花掉的时间，当然由于时间仓促，有可能搜集的信息不能到达目的地，这时请输出-1

Sample Input

2

3 2

1 2 2

2 3 3

1 3

4 2

1 2 3

1 3 2

1 4

Sample Output

5

-1

【分析】

经典bfs最短路径搜索....唔...也没什么好说的，最基本的搜索思路，因为n有1000所以显然n^3的floyd算法是不行的...所以需要bfs去搜，这个代码是完全凭自己对bfs理解写的一个代码，所以可能有点另类吧...数据有个小坑..看自己理解吧~

【代码】

#include <stdio.h>
#include <string.h>
using namespace std;
struct xx{
  int len;
  int s[1005];
  int co[1005];
}a[1005];

int p[20000],f[2000],cost[20000];


int find(int x,int y)
{
  int head=0;
  int end=1;
  memset(p,0,sizeof(p));
  memset(cost,0,sizeof(cost));
  p[0]=x;
  cost[0]=0;
  while (head<end)
  {
    int w=p[head];
    if (w==y|| f[w]<cost[head]) 
    {
      head++;
      continue;
    }
    for (int i=0;i<a[w].len;i++)
      if (!f[a[w].s[i]] || ( f[a[w].s[i]]>(cost[head]+a[w].co[i])) )
      {
        f[a[w].s[i]]=cost[head]+a[w].co[i];
        p[end]=a[w].s[i];
        cost[end]=f[a[w].s[i]];
        end++;
      }
    head++;
  }
  return f[y];
}

int main()
{
  int pp;scanf("%d",&pp);
  while (pp--)
  {
    int c,n,m,x,y;scanf("%d%d",&n,&m);
    for (int i=0;i<=n;i++) a[i].len=0;
    for (int i=0;i<m;i++)
    {
      scanf("%d%d%d",&x,&y,&c);
      a[x].s[a[x].len]=y;
      a[x].co[a[x].len]=c;a[x].len++;
      a[y].s[a[y].len]=x;
      a[y].co[a[y].len]=c;a[y].len++;
    }
    memset(f,0,sizeof(f));
    scanf("%d%d",&x,&y);
    if (x==y) printf("0\n");
    else
    {
      int ans=find(x,y);
      printf("%d\n",ans==0?-1:ans);    
    }
  }
  return 0;
}