hdu 2544 spfa算法模板

电玩女神 2022-08-03 05:15 163阅读 0赞

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    int dis[111];
    bool vis[111];
    int cnt[111];
    vector<pii>v[111];
    int n,m;
    queue<int> q;
    void init()
    {
        for(int i=0;i<=n;i++)v[i].clear();
        while(!q.empty())q.pop();
        mem(cnt,0);
        mem(vis,0);
        mem(dis,inf);
    }
    
    bool spfa()
    {
        dis[1]=0;
        q.push(1);
        cnt[1]++;
        vis[1]=1;
        while(!q.empty())
        {
            int now=q.front();
            q.pop();
            vis[now]=0;
            for(int i=0;i<(int)v[now].size();i++)
            {
                pii t=v[now][i];
                if(dis[t.first]>dis[now]+t.second)
                {
                    dis[t.first]=dis[now]+t.second;
                    if(!vis[t.first])
                    {
                        q.push(t.first);
                        vis[t.first]=1;
                        cnt[t.first]++;
                        if(cnt[t.first]>n)
                        {
                            return 0;
                        }
                    }
                }
            }
        }
        return 1;
    
    }
    
    int main()
    {
        while(~scanf("%d%d",&n,&m) && n)
        {
            init();
            for(int i=1;i<=m;i++)
            {
                int t1=in(),t2=in(),cost=in();
                v[t1].push_back(pii(t2,cost));
                v[t2].push_back(pii(t1,cost));
            }
            spfa();
            printf("%d\n",dis[n]);
        }
        return 0;
    }