2017年11月做的题ACM

11月25日 星期六 下午一点到 五点
The 13th Zhejiang Provincial Collegiate Programming Contest

k 大佬的代码

有时候单独的 数组 比结构体 写起来短 ,这个优先队列用的好,一个点入队列不超过两次,vis==1 直接 跳过

大佬写的代码 好好呀,好想背下来呀

#include<queue>  
#include<cstdio>  
#include<algorithm>  
using namespace std;
using namespace std;  
typedef long long LL;  
const int maxn = 2e5 + 10;  
int T, n, m, sz, x, y, a, b;  
int ft[maxn], nt[maxn], u[maxn], v[maxn], w[maxn], vis[maxn];  
LL ans1, ans2, dis[maxn];  
  
struct point  
{  
    LL x, y, z;  
    point(LL x, LL y, LL z) :x(x), y(y), z(z) {};  
    bool operator<(const point &a) const  
    {  
        return y == a.y ? z > a.z:y > a.y;  
    }  
};  
  
int main()  
{  
    scanf("%d", &T);  
    while (T--)  
    {  
        ans1 = ans2 = sz = 0;  
        scanf("%d%d", &n, &m);  
        for (int i = 0; i <= n; i++) dis[i] = ft[i] = -1, vis[i] = 0;  
        while (m--)  
        {  
            scanf("%d%d%d%d", &x, &y, &a, &b);  
            u[sz] = y;  v[sz] = a;  w[sz] = b;  nt[sz] = ft[x]; ft[x] = sz++;  
            u[sz] = x;  v[sz] = a;  w[sz] = b;  nt[sz] = ft[y]; ft[y] = sz++;  
        }  
        priority_queue<point> p;  
        p.push(point(0, 0, 0)); dis[0] = 0;  
        while (!p.empty())  
        {  
            point q = p.top();  p.pop();  
            if (vis[q.x]) continue; else vis[q.x] = 1;  
            ans1 += q.y;    ans2 += q.z;  
            for (int i = ft[q.x]; i != -1; i = nt[i])  
            {  
                if (dis[u[i]] == -1 || dis[u[i]] >= q.y + v[i])  
                {  
                    dis[u[i]] = q.y + v[i];  
                    p.push(point(u[i], dis[u[i]], w[i]));  
                }  
            }  
        }  
        printf("%lld %lld\n", ans1, ans2);  
    }  
    return 0;  
}  

11月26日
电子科技大学第九届ACM趣味程序设计竞赛

11月27日凌晨 00:05 Codefores

做了一道题 涨了 60几分吧 exciting

11月30号

HDU 4725
最短路
题意: 每一个点 在某一层,相邻层可以 花费 C代价,从一层的任意一点到达另一层的任意一个点。WA 到想哭o(╥﹏╥)o,还好没放弃, 建图建错啦,
错误: 每两层中间 建立2点 a,b 设置a-b长 c,下面那层到达a 点距离为 0,上一层到达b层为0,这样通过 相邻两层的代价就为 c, 这么看是没什么问题,但是,但是,如果 同一层 没有边,比如点 E1 E2 同一层,而且没有边,但是!!!这样 通过a点 让 E1->a ->E2 代价就变成 0!!

所有这样建边 不可取!

谢谢大佬的博客

每层 创建 a,b两点, 该层E点到达 a 单向边 权值为c, 相邻层 到达b 权值 为c, a到达相邻层权值 0,
b到达相邻层 权值为 0,这样 同一层不联通的点,代价 最少为 2*c (~ ̄▽ ̄)~

#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1000000+10;
int T,n,m,sz,x,y,a,c;
#define INF 0x7FFFFFFF
struct point{
int x,y;
point(int x,int y):x(x),y(y){};
bool operator<(const point &a)const
{
    return y>a.y;
}
};

int ans1,dis[maxn];
int  nt[maxn],u[maxn],v[maxn];
bool vis[maxn];
int ft[maxn];
void fun()
{
        priority_queue<point>p;
        p.push(point(1,0));
        dis[1]=0;
        while(p.size())
        {
            point q=p.top();p.pop();
            if(vis[q.x]) continue;
            else vis[q.x]=1;
            if(q.x==(n))
            {
                //cout<<" qx "<<q.x<<endl;
                ans1=q.y;
                break;
            }
            for(int i=ft[q.x];i!=-1;i=nt[i])
            {
                //cout<<" x "<<q.x<<" "<<u[i]<<" dis "<<dis[u[i]]<<endl;
                if(dis[u[i]]==-1||dis[u[i]]>q.y+v[i])
                {
                    dis[u[i]]=q.y+v[i];
                   // cout<<" x "<<q.x<<" "<<u[i]<<" ddd "<<dis[u[i]]<<endl;
                    p.push(point(u[i],dis[u[i]]));
                }
            }
        }
}
int dijkstra()
{
    priority_queue<point>p;
    for(int i=0;i<=3*n;i++)
        dis[i]=INF;
        dis[1]=0;
        p.push(point(1,0));
        while(!p.empty())
        {
            point q=p.top();p.pop();
            for(int i=ft[q.x];i!=-1;i=nt[i])
            {
                if(dis[u[i]]<=q.y+v[i])
                    continue;
                 //   cout<<q.x<<" "<<u[i]<<" "<<q.y+v[i]<<endl;
                p.push(point(u[i],dis[u[i]]=q.y+v[i]));
            }
        }
        return dis[n]==INF?-1:dis[n];
}
int main()
{
    scanf("%d",&T);
    for(int ca=1;ca<=T;ca++)
    {
        ans1=-1;sz=0;
        scanf("%d%d%d",&n,&m,&c);
        int temp=0;
        ft[0]=-1;
        for(int i=0;i<=3*n+1;i++)
        {
            ft[i]=-1;
            vis[i]=0;
            nt[i]=0;
            dis[i]=-1;
        }

      /*  for(int i=1;i<=n-1;i++)
        {
              u[sz]=i+n;v[sz]=c;nt[sz]=ft[i+2*n];ft[i+2*n]=sz++;
              u[sz]=i+2*n;v[sz]=c;nt[sz]=ft[i+n];ft[i+n]=sz++;
        }
       */

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&temp);
            u[sz]=n+temp;v[sz]=c;nt[sz]=ft[i];ft[i]=sz++;
            u[sz]=i;v[sz]=0;nt[sz]=ft[temp+2*n];ft[temp+2*n]=sz++;

            if(--temp)
            {
            u[sz]=i;v[sz]=0;nt[sz]=ft[n+temp];ft[n+temp]=sz++;
            u[sz]=2*n+temp;v[sz]=c;nt[sz]=ft[i];ft[i]=sz++;
            }
        }

        while(m--)
        {
            scanf("%d%d%d",&x,&y,&a);

            u[sz]=y;v[sz]=a;nt[sz]=ft[x];ft[x]=sz++;
            u[sz]=x;v[sz]=a;nt[sz]=ft[y];ft[y]=sz++;
        }

        printf("Case #%d: ",ca);
       // ans1=dijkstra();
       fun();
        if(n==0)
            ans1=0;
        printf("%d\n",ans1);
    }
    return 0;

}

//#include <cstdio>
//#include <algorithm>
//#include <queue>
//#include <cstring>
//using namespace std;
//typedef pair<int,int> PII;
//const int MAXN=3e5+7;
//const int MAXM=MAXN;
//const int INF=0x3f3f3f3f;
//int T,head[MAXN],to[MAXM<<1],ne[MAXM<<1],wt[MAXM<<1],n,m,dist[MAXN],ecnt;
//void init()
//{
//    ecnt=0;
//    memset(head,0,sizeof(head));
//}
//void addedge(int a,int b,int c)
//{
//    ne[++ecnt]=head[a];
//    head[a]=ecnt;
//    to[ecnt]=b;
//    wt[ecnt]=c;
//}
//int vis[MAXN];
//priority_queue<PII> pq;
//int dijkstra(int s,int t)//s为源点,t为终点,路径权值非负
//{
//    for(int i=1;i<=n;i++)
//        dist[i]=INF,vis[i]=0;
//    dist[s]=0;
//    pq.push(PII(0,s));
//    while(!pq.empty())
//    {
//        int milb=pq.top().second;
//        pq.pop();
//        if(vis[milb])
//            continue;
//        vis[milb]=1;
//        for(int j=head[milb];j;j=ne[j])
//        {
//            int v=to[j];
//            if(!vis[v]&&dist[v]>dist[milb]+wt[j])
//            {
//                dist[v]=dist[milb]+wt[j];
//                pq.push(PII(-dist[v],v));
//            }
//        }
//    }
//    if(dist[t]==INF)
//        return -1;
//    return dist[t];
//}
//int main()
//{
//    int ta,tb,tc;
//    scanf("%d",&T);
//    for(int kase=1;kase<=T;kase++)
//    {
//        init();
//        scanf("%d%d%d",&n,&m,&tc);
//        for(int i=1;i<=n;i++)
//        {
//            scanf("%d",&ta);
//            addedge(i,n+ta,tc);
//            addedge(2*n+ta,i,0);
//            if(--ta)
//            {
//                addedge(n+ta,i,0);
//                addedge(i,2*n+ta,tc);
//            }
//        }
//        for(int i=0;i<m;i++)
//        {
//            scanf("%d%d%d",&ta,&tb,&tc);
//            addedge(ta,tb,tc);
//            addedge(tb,ta,tc);
//        }
//        n*=3;
//        printf("Case #%d: %d\n",kase,dijkstra(1,n/3));
//    }
//    return 0;
//}

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,718评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,683评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,207评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,755评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,862评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,050评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,136评论 3 410
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,882评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,330评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,651评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,789评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,477评论 4 333
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,135评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,864评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,099评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,598评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,697评论 2 351

推荐阅读更多精彩内容

  • 1. 关于诊断X线机准直器的作用,错误的是()。 (6.0 分) A. 显示照射野 B. 显示中心线 C. 屏蔽多...
    我们村我最帅阅读 10,347评论 0 5
  • 【1】7,9,-1,5,( ) A、4;B、2;C、-1;D、-3 分析:选D,7+9=16;9+(-1)=8;(...
    Alex_bingo阅读 18,861评论 1 19
  • 每天早上月亮和星星还在 我已经踏上月台 看着和我一样奔波的人们 内心稍微释怀 每个不同的青春都有共同的未来 与自己...
    尚岸阅读 296评论 2 5
  • 时代是水流,答案是河岸,而问题是船只。 在水流不太快的时代,你在河岸上慢慢走,也能跟得上水流。但在知识爆炸的洪流时...
    花田馨语阅读 176评论 0 1
  • 三月的雨 带着料峭的寒 零星的洒落 稀落的行人 步履匆匆 三月的雨 天空是灰色的 笼罩着所有的情绪 枯黄的树枝被氤...
    诗与酒趁年华阅读 313评论 0 0