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;
}