poj 1797 最短路变形dijkstra

56 阅读 0 评论 37 点赞

我是靠谱客的博主无语灯泡，最近开发中收集的这篇文章主要介绍poj 1797 最短路变形dijkstra，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：题目大意：有n个城市，m条道路，在每条道路上有一个承载量，现在要求从1到n城市最大承载量，而最大承载量就是从城市1到城市n所有通路上的最大承载量

链接：点我
解题思路：其实这个求最大边可以近似于求最短路，只要修改下找最短路更新的条件就可以了

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 #define pb(a) push_back(a)
11 const int INF=0x3f3f3f3f;
12 const double eps=1e-5;
13 typedef long long ll;
14 #define cl(a) memset(a,0,sizeof(a))
15 #define ts printf("*****n");
16 const int MAXN=1010;
17 int n,m,tt,cnt;
18 int dist[MAXN][MAXN];
19 #define typec int
20 bool vis[MAXN];
21 int pre[MAXN];
22 int cost[MAXN][MAXN],lowcost[MAXN];
23 void Dijkstra(int n,int beg)
24 {
25     for(int i=1;i<=n;i++)
26     {
27         lowcost[i]=0;vis[i]=false;pre[i]=-1;
28     }
29     lowcost[beg]=INF;
30     for(int j=0;j<n;j++)
31     {
32         int k=-1;
33         int Min=0;
34         for(int i=1;i<=n;i++)
35         if(!vis[i]&&lowcost[i]>Min)
36         {
37             Min=lowcost[i];
38             k=i;
39         }
40         if(k==-1)break;
41         vis[k]=true;
42         for(int i=1;i<=n;i++)
43         if(!vis[i]&&min(lowcost[k],cost[k][i])>lowcost[i])
44         {
45             lowcost[i]=min(lowcost[k],cost[k][i]);
46             pre[i]=k;
47         }
48     }
49 }
50 int main()
51 {
52     int i,j,k;
53     #ifndef ONLINE_JUDGE
54     freopen("1.in","r",stdin);
55     #endif
56     int ca=1;
57     int tt;
58     scanf("%d",&tt);
59     while(tt--)
60     {
61         scanf("%d%d",&n,&m);
62         cl(cost);
63         int u,v,w;
64         cl(cost);
65         for(i=0;i<m;i++)
66         {
67             scanf("%d%d%d",&u,&v,&w);
68             cost[u][v]=cost[v][u]=max(cost[u][v],w);
69         }
70         /*for(i=1;i<=n;i++)
71         {
72             for(j=1;j<=n;j++)
73             {
74                 printf("%d ",cost[i][j]);
75             }
76             printf("n");
77         }*/
78         Dijkstra(n,1);
79         printf("Scenario #%d:n%dnn",ca++,lowcost[n]);
80     }
81     return 0;
82 }