HDU5137

hdu5137.cpp

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;

const int MAXN = 32;
const int MAXM = 1005;
const int INF = 0x3fffff;
int n,m,a,b,c;
int dis[MAXN];
int graph[MAXN][MAXN];
int graph2[MAXN][MAXN];
bool in_queue[MAXN];
queue<int> Q;
void init()
{
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            graph2[i][j]=graph[i][j]=i==j?0:INF;
}

int spfa(int s)
{
    for (int i=1;i<=n;i++) dis[i]=INF;
    memset(in_queue,0,sizeof(in_queue));
    while(!Q.empty())
    {
        Q.pop();
    }
    Q.push(s);
    in_queue[s]=1;
    dis[s]=0;
    while(!Q.empty())
    {
        int w = Q.front();
        Q.pop();
        in_queue[w] = 0;
        for (int i=1;i<=n;i++)
        {
            if (dis[i]>dis[w]+graph[w][i])
            {
                dis[i]=dis[w]+graph[w][i];
                if (!in_queue[i])
                {
                    Q.push(i);
                    in_queue[i]=1;
                }
            }
        }
    }
    return dis[n];
}

int main()
{
    while(~scanf("%d%d",&n,&m) && n)
    {
        init();
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            graph[a][b]=graph[b][a]=graph2[a][b]=graph2[b][a]=c;
        }
        int ans = 0;
        for (int i=2;i<=n-1;i++)
        {
            for (int j=1;j<=n;j++) graph[j][i]=graph[i][j]=INF;
            int shortest = spfa(1);
            ans = ans>shortest?ans:shortest;
            for (int j=1;j<=n;j++) graph[j][i]=graph[i][j]=graph2[i][j];
        }
        if (ans!=INF)
            cout << ans << endl;
        else cout << "Inf" << endl;
    }
}