石龙镇住房规划建设局网站,wordpress comment_count,深圳网站设计x,seo关键词优化哪个平台好前言
这是今天C组的题#xff0c;闲得无聊做了一会#xff0c;结果就对了233。这算是学了SPFA之后的第一次实战了。反正其他C组题我也不想做了。好了现在bi~~#xff08;系统自动屏蔽#xff09;也在做这道题。 还有这道题的名字叫
正题
题目
一个有向图#xff0c;有…前言
这是今天C组的题闲得无聊做了一会结果就对了233。这算是学了SPFA之后的第一次实战了。反正其他C组题我也不想做了。好了现在bi~~系统自动屏蔽也在做这道题。 还有这道题的名字叫
正题
题目
一个有向图有两个GPS它们认为每条边的长度不尽相同如果你走的路有GPS认为这不是最短路就会报警警告一次如果两个GPS都认为不是那就会警告2次要求警告次数最少。 Input
第一行整数N 和M。 接下来M 行第i 行有四个整数Ai,Bi, Pi,Qi 描述第i 条道路。
Output
输出单独一行一个整数——FJ 选择从他家到达农场的最佳线路之后路上收到的最小总警告数。
Sample Input
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
Sample Output
1
【样例解释】
输入详述
这里有5 个路口和7 条有向道路。第一条道路从路口3 到路口4 连接两个路口第一GPS 认为这条路需要7 单位时间来通过接着第二GPS 认为它只需1单位时间诸如此类。
输出详述
如果FJ 按照路线1-2-4-5 走那么第一GPS 会在1-2 这条路上发出警告它认为1-3 这条路更好。然而对于路线剩下的2-4-5两个GPS 都快乐地坐着FJ 的小车通过了因为每个GPS 都以为这是2 到5 的最短路。 解题思路
首先我们要分别算出2个GPS的每个点到达终点的最小值然后判断如果前一个点的最短路两点之间的权值不等于后一个点的最短路则这个GPS会认为这条路是错的。为了方便我们把有向图倒着存然后SPFA搜3次。 代码
#includecstdio
#includecstring
using namespace std;
struct line{int first,last,l1,l2,next;
};//邻接表
line a[50001];
int f[10001],f2[10001],ff[10001],n,m,ls[10001],state[10001],tail,head,p,w;
bool b[10001];
void spfaA()
{memset(f,127/3,sizeof(f));//初始化tail1;head0;f[n]0;state[1]n;b[n]true;//初始化do{head(head2)%n-1;//循环队列pls[state[head]];//找边while (p!0){if (f[a[p].first]a[p].l1f[a[p].last])//松弛{f[a[p].last]f[a[p].first]a[p].l1;if (!b[a[p].last]){tail(tail2)%n-1;//入队state[tail]a[p].last;b[a[p].last]true;}}pa[p].next;//下一条}b[state[head]]false;//解封}while (tail!head);
}
void spfaB()//一样的不解释
{memset(f2,127/3,sizeof(f2));tail1;head0;f2[n]0;state[1]n;b[n]true;do{head(head2)%n-1;pls[state[head]];while (p!0){if (f2[a[p].first]a[p].l2f2[a[p].last]){f2[a[p].last]f2[a[p].first]a[p].l2;if (!b[a[p].last]){tail(tail2)%n-1;state[tail]a[p].last;b[a[p].last]true;}}pa[p].next;}b[state[head]]false;}while (tail!head);
}
int check(int x)//判断该条边会有几个GPS报错
{int s0;if (f[a[x].first]a[x].l1!f[a[x].last]) s;//第一个GPSif (f2[a[x].first]a[x].l2!f2[a[x].last]) s;//第二个GPSreturn s;//返回
}
void spfa()
{memset(ff,127/3,sizeof(ff));tail1;head0;ff[n]0;state[1]n;b[n]true;do{head(head2)%n-1;pls[state[head]];while (p!0){wcheck(p);//代价if (ff[a[p].first]wff[a[p].last]){ff[a[p].last]ff[a[p].first]w;if (!b[a[p].last]){tail(tail2)%n-1;state[tail]a[p].last;b[a[p].last]true;}}pa[p].next;}b[state[head]]false;}while (tail!head);printf(%d,ff[1]);//输出
}
int main()
{freopen(gpsdual.in,r,stdin);freopen(gpsdual.out,w,stdout);scanf(%d%d,n,m);for (int i1;im;i){scanf(%d%d%d%d,a[i].last,a[i].first,a[i].l1,a[i].l2);a[i].nextls[a[i].first];ls[a[i].first]i;} spfaA();spfaB();spfa();
} 好了现在bi~~系统自动屏蔽做完了道题。
