Liny_@NotePad

沉迷ACG中

Til the Cows Come Home

YOYO posted @ 2008年11月25日 23:53 in 【ICPC】解题报告 with tags dijkstra 单源最短路径 , 1971 阅读

pku 2387：http://acm.pku.edu.cn/JudgeOnline/problem?id=2387

从n地走到1地，求最小距离。典型的单源最短路径，直接套模板……

  1. #include<iostream>
  2. #define N 1002
  3. #define MAX 99999
  4. using namespace std;
  5. int edges[N][N],d[N],n;
  6.  
  7. void dijkstra(int v)
  8. {
  9.         int i,j;
  10.         bool s[N]={false};
  11.         for(i=1;i<=n;i++)
  12.                 d[i]=edges[v][i];
  13.         d[v]=0;s[v]=true;
  14.         for(i=1;i<n;i++)
  15.         {
  16.                 int temp=MAX;
  17.                 int u=v;
  18.                 for(j=1;j<=n;j++)
  19.                         if((!s[j])&&(d[j]<temp))
  20.                         {
  21.                                 u=j;
  22.                                 temp=d[j];
  23.                         }
  24.                         s[u]=true;
  25.                         for(j=1;j<=n;j++)
  26.                                 if((!s[j])&&(edges[u][j]<MAX)&&(d[u]+edges[u][j])<d[j])
  27.                                         d[j]=d[u]+edges[u][j];
  28.         }
  29. }
  30.  
  31.  
  32. int main(){
  33.         int t;
  34.         cin>>t>>n;
  35.         for(int i=1;i<=n;i++){
  36.                 for(int j=1;j<=n;j++){
  37.                         edges[i][j]=MAX;
  38.                 }
  39.         }
  40.         while(t--){
  41.                 int a,b,s;
  42.                 cin>>a>>b>>s;
  43.                 if(edges[a][b]&&s>=edges[a][b])continue;
  44.                 edges[a][b]=edges[b][a]=s;
  45.         }
  46.         dijkstra(n);
  47.         cout<<d[1]<<endl;
  48.         return 0;
  49. }
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter