hdu2544 最短路（dijkstra/優先隊列）

最短路

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 39750    Accepted Submission(s): 17334

Problem Description

在每年的校賽裡，所有進入決賽的同學都會獲得一件很漂亮的t-shirt。但是每當我們的從業人員把上百件的衣服從商店運回到賽場的時候，卻是非常累的！是以現在他們想要尋找最短的從商店到賽場的路線，你可以幫助他們嗎？

Input

輸入包括多組資料。每組資料第一行是兩個整數N、M（N<=100，M<=10000），N表示成都的大街上有幾個路口，标号為1的路口是商店所在地，标号為N的路口是賽場所在地，M則表示在成都有幾條路。N=M=0表示輸入結束。接下來M行，每行包括3個整數A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A與路口B之間有一條路，我們的從業人員需要C分鐘的時間走過這條路。

輸入保證至少存在1條商店到賽場的路線。

Output

對于每組輸入，輸出一行，表示從業人員從商店走到賽場的最短時間

Sample Input

2 1

1 2 3

3 3

1 2 5

2 3 5

3 1 2

0 0

Sample Output

3

2

Source

​​UESTC 6th Programming Contest Online​​

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
struct node
{
  int pos,l;
  friend bool operator <(node x,node y)
  {
    return x.l>y.l;
  }
};
priority_queue<node>s;
int len[105][105],vis[105],n;
void dijkstra(int end)
{
  node temp,x;
  temp.l=0,temp.pos=1;
  s.push(temp);
  while(!s.empty())
  {
    temp=s.top(),x=temp;
    s.pop();
    int star=temp.pos;
    if(star==end)
    break;
    vis[star]=1;
    for(int i=2;i<=n;i++)
    {
      if(!vis[i]&&len[star][i]<2000)
      {
        temp.pos=i,temp.l+=len[star][i];
        s.push(temp);
      }
      temp=x;
    }
  }
  printf("%d\n",temp.l);
}
int main()
{
  int m;
  while(scanf("%d %d",&n,&m)!=EOF)
  {
    if(m==0&&n==0)
    break;
    memset(len,100,sizeof(len));
    memset(vis,0,sizeof(vis));
    for(int i=0;i<m;i++)
    {
      int a,b,x;
      scanf("%d %d %d",&a,&b,&x);
      if(x<len[a][b])
      len[a][b]=len[b][a]=x;
    }
    dijkstra(n);
    while(!s.empty())
    s.pop();
  }
  return 0;
}