2017年11月做的题ACM
2017-11-30 本文已影响13人
_弓长_大人
11月25日 星期六 下午一点到 五点
The 13th Zhejiang Provincial Collegiate Programming Contest
有时候单独的 数组 比结构体 写起来短 ，这个优先队列用的好，一个点入队列不超过两次，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;
//}
