Dijsktra&&Flyod

浏览数：20 / 时间：2015年06月09日

题目描述

大奶辉学长很懒，每次他出门都会按照最短路径找，现在给你大奶辉的起始位置，请输出其他点到这一点的最短距离。

输入

有多个测试样例，直到文件结束。

第一行是n,m,k分别代表点的数目和边的数目,以及询问的次数

接下来m行，输入代表着2个点间的距离。

接下来是k个询问i,j要输出的是i,j间的最短距离

输出

输出i,j两点间的最短距离

样例输入

6 10 2

1 2 6

1 4 5

1 3 1

2 3 5

2 5 3

3 4 5

3 5 6

3 6 4

4 6 2

5 6 6

2 3

2 4

样例输出

解法一：

Dijsktra

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 #define MAX 0x3f3f3f3f
 7 #define N 300
 8 int dis[N][N],vis[N],low[N];
 9 int n,m;
10  
11 void dijsktra(int st,int ed)
12 {
13     int pos=st,min,i;
14     memset(vis,0,sizeof(vis));
15     vis[pos]=1;
16     for (i=1;i<=n;i++)
17         low[i]=dis[pos][i];
18     low[pos]=0;
19     for (;;)
20     {
21         min=MAX;
22         for (i=1;i<=n;i++)
23          
24             if (!vis[i]&&low[i]<min)
25             {
26                 min=low[i];
27                 pos=i;
28             }
29             if (min==MAX)
30                 break;
31             vis[pos]=1;
32             for (i=1;i<=n;i++)
33             {
34                 if (!vis[i]&&low[i]>dis[pos][i]+low[pos])
35                 {
36                     low[i]=dis[pos][i]+low[pos];
37                 }
38             }   
39     }
40     printf("%d\n",low[ed]);
41 }
42 int main()
43 {
44     int i,j,a,b,w,num,x;
45     int ask1[100],ask2[100];
46     while (scanf("%d %d %d",&n,&m,&num)!=EOF)
47     {
48         for (i=1;i<=n;i++)
49          
50             for (j=1;j<=n;j++)
51             {
52                 dis[i][j]=dis[j][i]=MAX;
53             }
54             for (i=1;i<=m;i++)
55             {
56                 scanf("%d%d%d",&a,&b,&w);
57                 if (w<dis[a][b])
58                     dis[a][b]=dis[b][a]=w;
59             }
60             for (x=0;x<num;x++)
61             {
62                 scanf("%d%d",&ask1[x],&ask2[x]);
63                  
64             }
65             for (x=0;x<num;x++)
66                 dijsktra(ask1[x],ask2[x]);
67     }
68     return 0;
69 }

View Code

解法二：

Flyod

 1 #include <stdio.h>
 2 int maze[100][100];
 3 #define MAX 100000
 4  
 5 int min(int x,int y)
 6 {
 7     return y>x?x:y;
 8 }
 9  
10 void flyod(int n)
11 {
12     int k,i,j;
13     for (k=1;k<=n;k++)
14         {
15             for (i=1;i<=n;i++)
16             {
17                 for (j=1;j<=n;j++)
18                 {
19                     maze[i][j]=min(maze[i][j],maze[i][k]+maze[k][j]);
20                 }
21             }
22         }
23 }
24 int main()
25 {
26     int n,m,num;
27     int ask1[1000],ask2[1000];
28     while (scanf("%d%d%d",&n,&m,&num)!=EOF)
29     {
30         int i,j,x;
31          
32         for (i=1;i<=n;i++)
33         {
34             for (j=1;j<=n;j++)
35             {
36                 if (i==j)
37                     maze[i][j]=0;
38                 else
39                     maze[i][j]=MAX;
40             }
41         }
42         for (i=1;i<=m;i++)
43         {
44             int a,b,c;
45             scanf("%d%d%d",&a,&b,&c);
46             maze[a][b]=maze[b][a]=c;
47         }
48         for (x=0;x<num;x++)
49         {
50             scanf("%d %d",&ask1[x],&ask2[x]);
51         }
52         flyod(n);
53         for (x=0;x<num;x++)
54         {
55             printf("%d\n",maze[ask1[x]][ask2[x]]);
56         }
57     }
58     return 0;
59 }