「NOIP模拟赛」坑爹的GPS
坑爹的GPS（gpsduel.c/.cpp/.pas）
有一天，FJ买了一辆车，但是，他一手下载了两个GPS系统。好了现在麻烦的事情来了，GPS有一个功能大概大家也知道，如果FJ没有按照GPS内置地图的最短路走，GPS就会报错来骚扰你。现在FJ准备从他的农舍（在1这个点）开车到他的谷屋（n这个点）。FJ给了你两个GPS系统内置地图的信息，他想知道，他最少会听到多少次报错（如果FJ走的路同时不满足两个GPS，报错次数+2）
读入：第一行：n,k；n表示有FJ的谷屋在哪，同时保证GPS内置地图里的点没有超过n的点。K表示GPS内置地图里的路有多少条，如果两个点没有连接则表明这不是一条通路。
接下来k行，每行4个数X,Y,A,B分别表示从X到Y在第一个GPS地图里的距离是A，在第二个GPS地图里的是B。注意由于地形的其他因素GPS给出的边是有向边。
输出：一个值，表示FJ最少听到的报错次数。
样例输入：
5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5
样例输出：
1
解释
FJ选择的路线是1 2 4 5，但是GPS 1认为的最短路是1到3，所以报错一次，对于剩下的2 4 5，两个GPS都不会报错。
数据范围
N<=10000，至于路有多少条自己算吧。数据保证所有的距离都在2^31-1以内。
题解
三次最短路。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct data{int to,next,v1,v2;}e[50005],ed[50005]; int head[10005],h[10005],q[10005],d1[10005],d2[10005],dis[10005]; bool inq[10005]; int n,k,cnt; int u[50005],v[50005],w1[50005],w2[50005]; void ins(int u,int v,int w1,int w2) {e[++cnt].next=head[u];head[u]=cnt;e[cnt].to=v;e[cnt].v1=w1;e[cnt].v2=w2;} void spfa1() { memset(d1,127/3,sizeof(d1)); int t=0,w=1; q[0]=n;inq[n]=1;d1[n]=0; while(t!=w) { int now=q[t];t++;if(t==10001)t=0; for(int i=head[now];i;i=e[i].next) if(e[i].v1+d1[now]<d1[e[i].to]) { d1[e[i].to]=e[i].v1+d1[now]; if(!inq[e[i].to]) {q[w++]=e[i].to;inq[e[i].to]=1;if(w==10001)w=0;} } inq[now]=0; } } void spfa2() { memset(d2,127/3,sizeof(d2)); int t=0,w=1; q[0]=n;inq[n]=1;d2[n]=0; while(t!=w) { int now=q[t];t++;if(t==10001)t=0; for(int i=head[now];i;i=e[i].next) if(e[i].v2+d2[now]<d2[e[i].to]) { d2[e[i].to]=e[i].v2+d2[now]; if(!inq[e[i].to]) {q[w++]=e[i].to;inq[e[i].to]=1;if(w==10001)w=0;} } inq[now]=0; } } void spfa3() { memset(dis,127/3,sizeof(dis)); int t=0,w=1; q[0]=1;inq[1]=1;dis[1]=0; while(t!=w) { int now=q[t];t++;if(t==10001)t=0; for(int i=h[now];i;i=ed[i].next) if(ed[i].v1+dis[now]<dis[ed[i].to]) { dis[ed[i].to]=ed[i].v1+dis[now]; if(!inq[ed[i].to]) {q[w++]=ed[i].to;inq[ed[i].to]=1;if(w==10001)w=0;} } inq[now]=0; } } int main() { //freopen("gpsduel.in","r",stdin); //freopen("gpsduel.out","w",stdout); n=read(),k=read(); for(int i=1;i<=k;i++) { u[i]=read();v[i]=read();w1[i]=read();w2[i]=read(); ins(v[i],u[i],w1[i],w2[i]); } spfa1();spfa2(); for(int i=1;i<=k;i++) { ed[i].to=v[i];ed[i].next=h[u[i]];h[u[i]]=i; if(d1[v[i]]+w1[i]>d1[u[i]])ed[i].v1++; if(d2[v[i]]+w2[i]>d2[u[i]])ed[i].v1++; } spfa3(); printf("%d",dis[n]); return 0; } |
计数器 9854694
OI 课件=>
OI 课件=>
http://acdream.info/problem?pid=1007 在这题上跪了一遍又一遍。。求大神秒掉~
这题模数是1e10+7= =WA了好久