HDU 1535 Invitation Cards (POJ 1511)

两次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<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#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];
vector<lx>g[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;j<e[i];j++)
        {
            v=g[u][j].v,d=g[u][j].d;
            now.d=d,now.v=u;
            g[v].push_back(now);
        }
    }
}
int SPFA(int thend) // long long
{
    for(int i=1;i<=n;i++)
        dis[i]=INF,vis[i]=0;
    queue<int>q;
    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];j<g[u].size();j++)
        {
            int v=g[u][j].v;
            int d=g[u][j].d;
            if(dis[v]>dis[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%
    }
}

HDU 1535 Invitation Cards (POJ 1511),布布扣,bubuko.com

时间: 06-30

HDU 1535 Invitation Cards (POJ 1511)的相关文章

hdu 1535 Invitation Cards(有向图的来回最短路,要反向建图)

题目: 链接:点击打开链接 题意: 给一个图,求1到各点和各点到1最短路. 思路: 先spfa,然后反向建图,在spfa就行了. 代码: #include <iostream> #include <cstdio> #include <queue> #include <cstring> using namespace std; #define INF 100000000 const int N = 1000010; struct node{ int u,v,w

poj 1511 Invitation Cards (最短路)

Invitation Cards Time Limit: 8000MS   Memory Limit: 262144K Total Submissions: 33435   Accepted: 11104 Description In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They wa

HDU 1535 Invitation Cards (最短路,附SLF优化SPFA)

题目: http://acm.hdu.edu.cn/showproblem.php?pid=1535 题意: 有向图,求点1到点2-n的最短距离之和以及点2-n到点1的最短距离之和 方法: 1.跑1为原点的最短路 2.反向建图(把有向图的边反向,(u,v,w)变成(v,u,w)),跑1为原点的最短路 3.将两者距离之和加和即可(注意用 long long ,int会溢出) 1 void input() 2 { 3 scanf("%d%d", &n, &m); 4 g1.

POJ1511:Invitation Cards(最短路)

Invitation Cards Time Limit: 8000MS   Memory Limit: 262144K Total Submissions: 34743   Accepted: 11481 题目链接:http://poj.org/problem?id=1511 Description: In the age of television, not many people attend theater performances. Antique Comedians of Malidi

hdu 1535 Invitation Cards 大年初一首A 一次正向SPFA+一次逆向SPFA

Invitation Cards Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2311    Accepted Submission(s): 1125 Problem Description In the age of television, not many people attend theater performances.

hdu 1535 Invitation Cards(SPFA)

Invitation Cards Time Limit : 10000/5000ms (Java/Other)   Memory Limit : 65536/65536K (Java/Other) Total Submission(s) : 28   Accepted Submission(s) : 14 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem Description In the age of telev

HDU - 1535 Invitation Cards 前向星SPFA

Invitation Cards In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards wit

poj 1511 Invitation Cards(dijstra优化)

题目链接:http://poj.org/problem?id=1511 题意:给出n个点和n条有向边,求所有点到源点1的来回最短路之和(保证每个点都可以往返源点1) 题目比较简单就是边和点的个数有点多所以可以用dijstra+优先队列这样复杂度就可以到v*logn #include <iostream> #include <cstring> #include <string> #include <vector> #include <queue>

HDU 1432 Lining Up (POJ 1118)

枚举,枚举点 复杂度为n^3. 还可以枚举边的,n*n*log(n). POJ 1118 要判断0退出. #include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list&