随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    给定图上的n个点及m条点间连线,试求从S点到W点的最短距离,若不存在,则输出-1;  
 4 How to Do:    经典的最短路算法的应用,dijkstra算法自编写
 5   */
 6 #include <iostream>
 7 using namespace std;
 8 int n,m;//点的个数,点间连线的条数
 9 int path[205][1005];
10 bool node[205];
11 int Dijkstras(int s,int w){
12     int i,j;
13     node[s]=true;
14     for(i=0;i<n;i++){
15         int mins=INT_MAX,pos=s;
16         for(j=0;j<n;j++){//寻找为选入点的最小值
17             if(!node[j]&&mins>path[s][j]){
18                 mins=path[s][j]; pos=j;
19             }
20         }
21         if(mins==INT_MAX||j>n)    break;
22         node[pos]=true;
23         for(j=0;j<n;j++){
24             if(!node[j]&&path[pos][j]!=INT_MAX&&path[s][j]>path[s][pos]+path[pos][j]){
25                 path[s][j]=path[s][pos]+path[pos][j];
26                 path[j][s]=path[s][j];
27             }
28         }
29     }
30     return path[s][w];
31 }
32 int main(){
33     //freopen("in.txt","r",stdin);
34     while(scanf("%d%d",&n,&m)!=EOF){
35         int i,j;
36         for(i=0;i<n;i++){
37             node[i]=false;
38             for(j=0;j<n;j++){
39                 if(j==i)    path[i][j]=0;
40                 else    path[i][j]=INT_MAX;//表示两点间无通路
41             }
42         }
43         for(i=0;i<m;i++){
44             int begin,end,len;
45             scanf("%d%d%d",&begin,&end,&len);
46             if(len<path[begin][end])//此处是全题关键,WA了很久。。。。【审题要细致啊】
47                 path[begin][end]=path[end][begin]=len;//双向赋值
48         }
49         int s,w;
50         scanf("%d%d",&s,&w);
51         if(s>w){
52             s=s^w;w=s^w;s=s^w;
53         }
54         if(s==w)
55             printf("0\n");
56         else{
57             int ans=Dijkstras(s,w);
58             if(ans==INT_MAX)    printf("-1\n");
59             else    printf("%d\n",ans);
60         }
61     }
62     return 0;
63 }
posted on 2012-03-04 12:30 Leo.W 阅读(225) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理