TOJ 3744: Transportation Costs 最短路 Spfa

左手的ㄟ右手 2022-05-25 23:43 142阅读 0赞

题目链接：http://210.32.82.1/acmhome/problemdetail.do?&method=showdetail&id=3744

这道题对我而言有点难度...一开始想不好怎么去判断....然后发现可以找到从起点/终点出发到每个点的最短路，这样遍历之后，就可以空缺一条边作为“免费”的，然后得到最小值就可以了。

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <queue>
    #include <map>
    #include <vector>
    #include <cstring>
    using namespace std;
    const int INF = 0x7fffffff;
    const int maxn = 110;
    vector<pair<int, int> > g[maxn+10];
    bool inque[maxn+10];
    void spfa(int s, int d[]) 
    {
    	queue<int> Q;
        int i;
        for(i=1;i<maxn;i++) 
    	d[i]=INF;
        d[s]=0;
        while(!Q.empty())
    		Q.pop();
        Q.push(s);
        inque[s]=true;
        while(!Q.empty()) 
    	{
            int u=Q.front();
            Q.pop();
            for(i=0;i<g[u].size();i++) 
    		{
                int t=g[u][i].first;
                if(d[u]+g[u][i].second<d[t]) 
    			{
                    d[t]=d[u]+g[u][i].second;
                    if(!inque[t]) 
    				{
                        inque[t]=true;
                        Q.push(t);
                    }
                }
            }
            inque[u]=false;
        }
    }
    int main()
    {
        int i,j,x,u,v,w,gn,gm;
        int d1[maxn],d2[maxn];
        pair<int,int> t;
        while(scanf("%d%d",&gn,&gm) != EOF) 
    	{
            for(i=1;i<=gn;i++) 
            g[i].clear();
            for(i=1;i<=gm;i++) 
    		{
                scanf("%d%d%d",&u,&v,&w);
                t.first=v;
                t.second=w;
                g[u].push_back(t);
                t.first=u;
                t.second=w;
                g[v].push_back(t);
            }
    		//计算起点/终点到每个点的最短路，然后遍历 
            spfa(1,d1);
            spfa(gn,d2);
            int mindis=INF;
    	    for(i=1;i<=gn;i++) 
    		{
    	        for(j=0;j<g[i].size();j++) 
    			{
    	            x=g[i][j].first;
    	            if(d1[i]!=INF&&d2[i]!=INF&&d1[i]+d2[x]<mindis) 
    	            mindis=d1[i]+d2[x];
    	        }
    	    }
    	    if(mindis!=INF) 
    	        printf("%d\n",mindis);    
    	    else
    	        printf("-1\n");
        }
        return 0;
    }