下雪了

POJ – 1797 Heavy Transportation (最短路/Dijkstra模板)

模板题emmm

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

int mp[1001][1001];
bool v[1001];
int dis[1001];
int n;

void dj(int x)
{
    mes(v, 0);
    v[x] = true;
    ffor(i, 1, n) dis[i] = mp[x][i];
    int pos;
    ffor(x, 1, n - 1)
    {
        int m = 0;
        ffor(i, 1, n)
        {
            if (!v[i] && dis[i] > m)
            {
                pos = i;
                m = dis[i];
            }
        }
        v[pos] = true;
        ffor(i, 1, n)
            if (!v[i])
                dis[i] = max(dis[i], min(dis[pos], mp[pos][i]));
    }
}

signed main()
{
    int T;
    while (cin >> T)
    {
        ffor(t, 1, T)
        {
            int m;
            scanf("%lld%lld", &n, &m);
            ffor(i, 1, n)
            {
                ffor(k, i + 1, n)
                    mp[i][k] = mp[k][i] = 0;
            }
            while (m--)
            {
                int a, b, c;
                scanf("%lld%lld%lld", &a, &b, &c);
                mp[a][b] = mp[b][a] = max(mp[a][b], c);
            }
            dj(1);
            cout << "Scenario #" << t << ":" << endl << dis[n] << endl << endl;
        }
    }
}

 


Add Your Comment

* Indicates Required Field

Your email address will not be published.

*