程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1535 Invitation Cards （POJ 1511）

HDU 1535 Invitation Cards （POJ 1511）

編輯：C++入門知識

兩次SPFA。求來和回的最短路之和。

用Dijkstra+鄰接矩陣確實好寫+方便交換，但是這個有1000000個點，矩陣開不了。

d1[]為 1~N 的最短路。

將所有邊的鄰點交換。

d2[] 為 1~N 的最短路。

所有相加為所要答案。

憂傷的是用SPFA “HDU 1535” AC了，但是POJ 一樣的題 “POJ 1511” 就WA了。

然後強迫症犯了，不停的去測試。

題意中找到一句關鍵話：Prices are positive integers the sum of which is smaller than 1000000000

本來int 可以的。HDU 就是這樣。

然後我就把POJ的求和改成了 long long 。還是WA。

然後發現我的INF 有問題，0xfffffff 不夠。然後改成0x7fffffff int的最大值，AC了。

POJ 數據也真是屌。完全不看題意的。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x7fffffff
#define eps 1e-6
using namespace std;
int n,m;
struct lx
{
    int v,d;
};
int dis[1000001];
bool vis[1000001];
int e[1000001];
vectorg[1000001];
void swapg()
{
    for(int i=1;i<=n;i++)
        e[i]=g[i].size();
    for(int i=1;i<=n;i++)
    {
        int u,v,d;
        lx now;
        u=i;
        for(int j=0;jq;
    dis[1]=0,vis[1]=1;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int j=e[u];jdis[u]+d)
            {
                dis[v]=dis[u]+d;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    int ans=0; //long long
    for(int i=1;i<=n;i++)
        ans+=dis[i];
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        int u,v,d;
        lx now;
        for(int i=1;i<=n;i++)
            g[i].clear();
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&d);
            now.d=d;
            now.v=v;
            g[u].push_back(now);
        }
        memset(e,0,sizeof(e));
        int dis1=SPFA(n); //long long
        swapg();
        int dis2=SPFA(n); //long long
        printf("%d\n",dis1+dis2); // lld%
    }
}