POJ 2253 Frogger
题意：给出n个坐标，一只青蛙在坐标1，它要跳到坐标2的位置，问每一次跳的最近的距离是多少。保留3位小数。
给出n个点的坐标，可以构造出一张强连通图。主要思想是Dijkstra，那么可以这样想，
设ans是最短的跳跃距离；
第一步：从点1 到其余没走过的点，找最短距离的点t1，记录最短距离m1，更新ans，并把点t1标记为走过。如果t1是点2 的话那么1-2的最短距离就是ans记录并退出，否则以点t1为中介点，更新其余各点到点1的距离；
第二步：从点1 到其余没走过的点，找最短距离的点t2，记录最短距离m2，更新ans，并把点t2标记为走过。如果t2是点2 的话那么1-2的最短距离就是ans记录并退出，否则以点t2为中介点，更新其余各点到点1的距离；
第三步：…
最多会循环n次，就会找点2.如果中间某一次找到了直接输出ans就行了。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define inf 0x3f3f3f
int x[210],y[210];
int n;
double mapp[210][210];
void Dij()
{
bool vis[210];//标记数组
double d[210];//点1到其余个点的距离
double ans=0;//最短的一次跳跃距离
memset(vis,0,sizeof(vis));
for(int i=1; i<=n; i++)
d[i]=mapp[1][i];
vis[1]=1;
for(int i=2; i<=n; i++)
{
int t;
double m=inf;
// 每次寻找从1到各个节点的最短路径，然后根据这个最短路径再去松弛其他点的路径，
//因为总共会松弛n次节点，所有2号节点可以 1，出现在松弛的过程中；2出现在最后一次松弛。
//总之在松弛完全所有节点之前，一定会找到2号节点。
for(int j=2; j<=n; j++)
if(!vis[j] && d[j]<m)
{
m=d[j];
t=j;
}
ans=max(ans,m);
vis[t]=1;
if(t==2)
{
printf("%.3f
",ans);
return;
}
for(int j=2; j<=n; j++)
{
if(!vis[j] && d[j]>mapp[t][j])
d[j]=mapp[t][j];
}
}
//printf("%.3f
",ans);
}
int main()
{
int cc=1;
while(scanf("%d",&n)!=EOF,n)
{
memset(mapp,0,sizeof(mapp));
for(int i=1; i<=n; i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
//构造连通图
mapp[i][j]=mapp[j][i]=sqrt( (x[i]-x[j])*(x[i]-x[j])*1.0+(y[i]-y[j])*(y[i]-y[j])*1.0 );
}
}
printf("Scenario #%d
",cc++);
printf("Frog Distance = ");
Dij();
}
return 0;
}
POJ 1797 Heavy Transportation
题意：有n个点和m条边。每个边有承受的最大容量，找一条路径，使得这条路径的容量最大。
这道题和上面的思路和方法是一样的，所以直接就放在一起了。不说多直接上代码。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define inf 0x3f3f3f
int n,m;
int mapp[1100][1100];
void Dij()
{
bool vis[1100];//标记数组
int d[1100];//点1到个点的距离
int ans=inf;//最大容量
memset(vis,0,sizeof(vis));
memset(d,0,sizeof(d));
for(int i=1; i<=n; i++)
d[i]=mapp[1][i];
vis[1]=1;
for(int i=2; i<=n; i++)
{
int mm=0;
int t;
for(int j=2; j<=n; j++)
if(!vis[j] && mm<d[j])
{
mm=d[j];
t=j;
}
ans=min(ans,mm);
vis[t]=1;
if(t==n)
{
printf("%d
",ans);
return;
}
for(int j=2; j<=n; j++)
{
if(!vis[j] && d[j]<mapp[t][j])
{
d[j]=mapp[t][j];
}
}
}
printf("%d
",ans);
}
int main()
{
int t;
int cc=1;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(mapp,0,sizeof(mapp));
for(int i=1; i<=m; i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
if(mapp[x][y]<c)
mapp[x][y]=mapp[y][x]=c;
}
printf("Scenario #%d:
",cc++);
if(n==1)
printf("0
");
else
Dij();
printf("
");
}
return 0;
}