poj 1511 Invitation Cards dijkstra+heap

     最近没有状态,不太难得一题,TLE了3次,WA了1次。

     这题主要就是要正向,逆向两次dijkstra,因为稀疏图,所以用heap优化有明显作用。

     注意会超出int范围,要用long long

    代码太挫了,越写越挫,估计到瓶颈期了

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
long long d[1000001];
bool vis[1000001];
int n;
int u[1000001],va[1000001];
int first[1000001],next[1000001],cnt,m;
int vf[1000001],vnext[1000001],vu[1000001],vvalue[1000001],vcnt;
int T;
struct node
{
    int v,x;
    friend bool operator <(node a,node b)
    {
        return a.v>b.v;
    }
    node(int a,int b)
    {
        v=a,x=b;
    }
    node()
    {
    }
};
void add(int vn,int un,int t)
{
    next[cnt]=first[vn];
    u[cnt]=un;
    va[cnt]=t;
    first[vn]=cnt++;

    vnext[vcnt]=vf[un];
    vu[vcnt]=vn;
    vvalue[vcnt]=t;
    vf[un]=vcnt++;
}
priority_queue<node> q;
void dijkstra(int x)
{
    memset(d,127,(n+1)*sizeof(d[0]));
    memset(vis,0,(n+1)*sizeof(vis[0]));
    while(!q.empty())q.pop();
    d[x]=0;
    q.push(node(d[x],x));
    int i,t,v;
    while(!q.empty())
    {
        v=q.top().x;q.pop();
        if(vis[v])continue;
        vis[v]=1;
        for(i=first[v];i!=-1;i=next[i])
        {
            if(d[u[i]]<=(t=d[v]+va[i]))continue;
            d[u[i]]=t;
            q.push(node(d[u[i]],u[i]));
        }
    }
}
void di2(int x)
{
    memset(d,127,(n+1)*sizeof(d[0]));
    memset(vis,0,(n+1)*sizeof(vis[0]));
    while(!q.empty())q.pop();
    d[x]=0;
    q.push(node(d[x],x));
    int i,t,v;
    while(!q.empty())
    {
        v=q.top().x;q.pop();
        if(vis[v])continue;
        vis[v]=1;
        for(i=vf[v];i!=-1;i=vnext[i])
        {
            if(d[vu[i]]<=(t=d[v]+vvalue[i]))continue;
            d[vu[i]]=t;
            q.push(node(d[vu[i]],vu[i]));
        }
    }
}
int main()
{
    int i,a,b,t;
    scanf("%d",&T);
    memset(next,-1,sizeof(next));
    memset(first,-1,sizeof(first));
    memset(vnext,-1,sizeof(vnext));
    memset(vf,-1,sizeof(vf));
    while(T--)
    {
        scanf("%d%d",&n,&m);
        cnt=0;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&t);
            add(a,b,t);
        }
        long long ans=0;
        dijkstra(1);
        for(i=2;i<=n;i++) ans+=d[i];
        di2(1);
        for(i=2;i<=n;i++) ans+=d[i];
        printf("%lld\n",ans);
        memset(next,-1,(m+1)*sizeof(next[0]));
        memset(first,-1,(n+1)*sizeof(first[0]));
        memset(vnext,-1,(m+1)*sizeof(vnext[0]));
        memset(vf,-1,(n+1)*sizeof(vf[0]));
    }
}
时间: 2024-02-19 11:19:36

poj 1511 Invitation Cards dijkstra+heap的相关文章

HDU 1535 Invitation Cards:多源点到单点最短路

链接: http://acm.hdu.edu.cn/showproblem.php?pid=1535 题目: Invitation Cards Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1044    Accepted Submission(s): 459 Problem Description In the age of te

hdu 1535 Invitation Cards

点击打开链接hdu1535 思路:最短路+SPFA 分析: 1 题目要求的是总的最小的花费,意思就是要求每一个人的花费都最小. 2 由于每一个人都是从1出去,最后还是都要回到1的,那么求解的时候就要分成两部分"出去+回来":出去的话直接利用SPFA(1),1作为起点即可求出每一点的最小花费,回来的话如果是直接利用对每一个人进行SPFA,那么这样肯定超时.仔细想想要求的是每一个点到1的最小距离,那么由于给定的是一个有向图,那么只要重新建图把边反向,那么我们所求的问题就变成1到每一个点的最

POJ 最短路问题题号汇总

求最短路基本的算法: 1>Dijkstra算法2>Bellman-Ford算法3>Floyd算法4>Floyd-Warshall算法5>Johnson算法6>A*算法 题目: 1.poj1062 昂贵的聘礼(中等)     此题是个经典题目:用Dijkstra即可:但是其中的等级处理需要一定的技巧:    要理解好那个等级制度:这个处理好,基本就是裸体Dijkstra: 2 poj1125 Stockbroker Grapevine(基本)    这个是简单Floyd,

最短路专题【完结】

第一题 hdu 1317 XYZZY 点击打开hdu 1317 思路: 1 题目的图是一个有向图,并且可能存在环.第一个点的能量值为100,边的权值利用能量大小,例如2点为-60,如果1->2那么value[1][2] = -602 题目明确指出如果是要win的话,那么必须是经过的每条边都要大于0.那么我们只要把那些经过松弛操作后的点大于0的入队即可,小于等于0的点肯定不会出现在最终的路径上.3 如果存在正环的话,那么就有能量值无限大,那么这个时候只要判断这个点能否到达n4 判断是否是有环还是五

POJ题目分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

poj分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

[算法系列之三十]Dijkstra单源最短路径算法

单源最短路径问题 给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数.另外,还给定 V 中的一个顶点,称为源.现在我们要计算从源到所有其他各顶点的最短路径长度.这里的长度是指路上各边权之和.这个问题通常称为单源最短路径问题. 前面Bellman-Ford最短路径算法讲了单源最短路径的Bellman-Ford算法(动态规划算法).这里介绍另外一个更常见的算法Dijkstra算法. Dijkstra算法和 最小生成树Prim算法最小生成树算法非常类似,大家可以先熟悉下个算法.两个算法

二叉堆(binary heap)

堆(heap) 亦被称为:优先队列(priority queue),是计算机科学中一类特殊的数据结构的统称.堆通常是一个可以被看做一棵树的数组对象.在队列中,调度程序反复提取队列中第一个作业并运行,因而实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权.堆即为解决此类问题设计的一种数据结构. 本文地址:http://www.cnblogs.com/archimedes/p/binary-heap.html,转载请注明源地址. 逻辑定义 n个

MonetDB heap bug?

接前面的测试 :  http://blog.163.com/digoal@126/blog/static/1638770402014714104326879/ 本文用到的2个测试表, 分别有60个字段, 其中1个字段为INT, 全唯一, 其他varchar(64), 全随机. 其中一个表b 5000万记录, 另一个表c 2500万记录. 数据库总共占用215GB. 数据库服务器内存+SWAP一共97GB. 但是执行某些查询的时候, 数据库目录会暴增到1.1TB, 例如 不带INT类型的分组查询.