poj3613

注意最短路转移的单位元是对角线为0，其它为INF。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <cstring>

#include <map>

#include <queue>

#include <set>

#include <cassert>

#include <stack>

#include <bitset>

#define mkp make_pair

using namespace std;

const double EPS=1e-;

typedef long long lon;

const lon SZ=,SSZ=*SZ,one=,INF=0x7FFFFFFF,mod=;

int n,m,S,T,mnum;

int mp[SZ][SZ];

struct nd{

    int len,bg,fn;

    nd(int a=,int b=,int c=):len(a),bg(b),fn(c){}

};

nd arr[SZ];

vector<int> ls;

int getid(int x)

{

    return lower_bound(ls.begin(),ls.end(),x)-ls.begin()+;

}

void init()

{

    cin>>n>>m>>S>>T;

    for(int i=;i<=m;++i)

    {

        cin>>arr[i].len>>arr[i].bg>>arr[i].fn;

        ls.push_back(arr[i].bg);

        ls.push_back(arr[i].fn);

    }

    sort(ls.begin(),ls.end());

    ls.erase(unique(ls.begin(),ls.end()),ls.end());

    mnum=ls.size();

    for(int i=;i<=mnum;++i)

    {

        for(int j=;j<=mnum;++j)

        {

//            if(i==j)mp[i][j]=0;

//            else

            mp[i][j]=(<<);

        }

    }

    for(int i=;i<=m;++i)

    {

        int bg=getid(arr[i].bg);

        int fn=getid(arr[i].fn);

        mp[bg][fn]=mp[fn][bg]=arr[i].len;

    }

}

void mul(int dst[][SZ],int x[][SZ],int y[][SZ])

{

    int res[SZ][SZ];

    memset(res,0x3f,sizeof(res));

//    for(int i=1;i<=mnum;++i)

//    {

//        for(int j=1;j<=mnum;++j)

//        {

//            res[i][j]=(1<<29);

//        }

//    }

    for(int i=;i<=mnum;++i)

    {

        for(int j=;j<=mnum;++j)

        {

            for(int k=;k<=mnum;++k)

            {

                res[i][j]=min(res[i][j],x[i][k]+y[k][j]);

            }

        }

    }

    for(int i=;i<=mnum;++i)

    {

        for(int j=;j<=mnum;++j)

        {

            dst[i][j]=res[i][j];

        }

    }

}

void work()

{

    int res[SZ][SZ],ele[SZ][SZ];

    memset(res,0x3f,sizeof(res));

    for(int i=;i<=mnum;++i)res[i][i]=;

    memcpy(ele,mp,sizeof(mp));

    for(;n;n/=)

    {

        if(n&)mul(res,res,ele);

        mul(ele,ele,ele);

    }

    S=getid(S),T=getid(T);

    cout<<res[S][T]<<endl;

}

int main()

{

    std::ios::sync_with_stdio();

    //freopen("d:\\1.txt","r",stdin);

    int casenum;

    //cin>>casenum;

    //cout<<casenum<<endl;

    //for(int time=1;time<=casenum;++time)

    //for(int time=1;cin>>n>>m;++time)

    {

        //printf("Case #%d:\n",time);

        init();

        work();

    }

    return ;

}