poj-2253

题意

• 复制一下别人的题意，有两只青蛙和若干块石头，现在已知这些东西的坐标，两只青蛙A坐标和青蛙B坐标是第一个和第二个坐标，现在A青蛙想要到B青蛙那里去，并且A青蛙可以借助任意石头的跳跃，而从A到B有若干通路，问从A到B的所有通路上的最大边

• 从a到b有n条路径, 寻找n条路经中边最大长度最小的

• code

/**********************************************************
    > File Name : 2253.cpp
    > Author : Wqr_
    > Mail : xueduanwei@126.com
    > Created Time : 19 03 19 18:47:31
**********************************************************/
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
#define INF 1<<28
using namespace std;
typedef pair<int , int> point;
point ps[250];
int n;
double d[250];
bool used[250];
double map[250][250];
void getdis(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            map[i][j] = INF;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i == j){
                map[i][j] = 0;
                continue;
            }else{
                double dis;
                dis = sqrt(pow((double)(ps[i].first - ps[j].first), 2) + pow((double)(ps[i].second - ps[j].second), 2));
                map[i][j] = dis;
                map[j][i] = dis;
            }
        }
    }
}
void diji(int f){
    fill(d, d + n, INF);
    memset(used, 0, sizeof(used));
    d[f] = 0;
    while(true){
        int v = -1;
        double mind = INF;
        for(int u = 0; u < n; u++){
            if(!used[u] && (v == - 1 || d[u] < mind)){
                v = u;
                mind = d[u];
            }
        }
        if(v == -1) break;
        used[v] = 1;
        for(int u = 0; u < n; u++){
            // 更新的是f号石头到u号石头最长边中的最小边
            d[u] = min(d[u], max(d[v],map[v][u]));
        }
    }
}
int main(){
    int kase = 0;
    while(cin >> n){
        if(n == 0) break;
        int a, b;
        for(int i = 0; i < n; i++){
            cin >> a >> b;
            ps[i].first = a;
            ps[i].second = b;
        }
        getdis();
        diji(0);
        printf("Scenario #%d\n", ++kase);
        printf("Frog Distance = %.3f", d[1]);
        printf("\n");
        printf("\n");
    }
    return 0;
}

• 关于Dijkstra成立条件的一篇博文

poj-1797

题意

• 上一个是找所有路径中最长路径最短的, 这个是找所有路径中最短路径最长的

• code

/**********************************************************
    > File Name : 1797.cpp
    > Author : Wqr_
    > Mail : xueduanwei@126.com
    > Created Time : 19 03 19 20:58:42
**********************************************************/
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
#include <queue>
#define INF 1<<28
#define MINF -1
using namespace std;
int map[1050][1050];
int book[1050];
int n, k;
int d[1050];
void diji(){
    for(int i = 0; i < n; i++){
        d[i] = map[0][i];
        book[i] = 0;
    }
    d[0] = 0;
    for(int i = 0; i < n; i++){
        int maxd = -1;
        int t;
        for(int j = 0; j < n; j++){
            if(!book[j] && d[j] > maxd){
                maxd = d[j];
                t = j;
            }
        }
        book[t] = 1;
        for(int j = 1; j < n; j++){
            if(!book[j] && d[j] < min(d[t], map[t][j])){
                d[j] = min(d[t], map[t][j]);
            }
        }
    }
}
int main(){
    int kase = 0;
    int num;
    cin >> num;
    while(num--){
        cin >> n >> k;
        int a, b, c;
        memset(map, -1, sizeof(map));
        for(int i = 0; i < k; i++){
            cin >> a >> b >> c;
            map[a - 1][b - 1] = c;
            map[b - 1][a - 1] = c;
        }
        diji();
        /*
        for(int i = 0; i < n; i++){
            cout << d[i] << " ";
        }
        */
        printf("Scenario #%d:\n", ++kase);
        printf("%d\n\n", d[n - 1]);
    }
    return 0;
}