A国交通部钦赐了一条从城市一到都市N的门道,经由一条公路或多条公路

公路通行税(Ceoi9玖)

版权表明:本篇小说版权归作者YJSheep(www.cnblogs.com/yangyaojia)全部,转发请保留原地点!

在PALMIA国家内,有N个城市由公路相接(每条公路恰好双向连接多少个都市)。经由一条公路或多条公路,从任壹城市出发能够抵达任何依次城市。直到今年,公路上才要征收公路通行税。在每条公路的高级中学级,有一征税员,从每一辆经因而路的车收取
1 PALMIA COIN(壹PC)。

内阁管理者决定削减收税员而举行公路印花。假诺一辆车欲进入一条公路,就务须将那张印花贴在窗上。

当局管理者决定:一年的公路印花的价值约等于在五个最远城市里面开展一百次旅行所需的资费。四个城市之间的离开是从一个都市到达第二个都市所需经过的最少数目标公路数。

您的天职是编写1个主次总结出公路印花的价值。

输入数据:

输入文件中包罗几组数据。每组的第三行李包裹含整数N和M(中间被1个空格隔绝),N是该国家中城市的数码,M是公路的数额(壹≦N≦1000,一≦M≦3000)。城市由整数举办编号,从1到N。接下来的M行,每行均包罗1对整数A,B(一≦A,B≦N),中间由1空格隔断,代表在都市A与B之间有一条公路。在终极一组数后仅有一行,是八个0,中间被1空格隔离。

输出数据:

对输入文件中的各组数据,输出文件中蕴藏壹行,表示公路印花的价值。

输入输出示例:

TOLLS.IN:

4 4

1 2

2 3

4 2

3 4

0 0

TOLLS.OUT:

200

解题报告

简言之的话正是摸索图的直径,因为数量n<=一千,对于每一种点用最短路为O(n*nlogn)是过不了的,但注意到路径长度唯有一,所以大家得以用BFS,时间勉勉强前病故。可是,大家能够先对有个别点用单源最短路。然后记录距离其最远的点,再相继对他们用BFS,那样功效会快很多而且答案也是不易的。

#include<bits/stdc++.h>
#define MAXN 1000+1
#define MAXM 500000+1
#define Pair pair<int,int>
using namespace std;
int n,m,t,v[MAXN],num;
int head[MAXN],g[MAXN][MAXN];
queue<Pair> emp;
struct Edge{
    int dis;
    int to,next;
}edge[MAXM];
int read()
{
    int in=0;
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar()) in=in*10+ch-'0';
    return in;
}
void add(int from,int to,int dis)
{
    edge[++num].next=head[from];
    edge[num].to=to;
    edge[num].dis=dis;
    head[from]=num;
}
void bfs(int s,int &maxl)
{
    memset(v,0,sizeof(v));
    queue<Pair> h=emp;
    h.push(Pair(0,s));
    while(h.size()>0)
    {
        int k=h.front().second,diss=h.front().first;h.pop();v[k]=1;
        for(int i=head[k];i;i=edge[i].next)
            if (v[edge[i].to]==0)
            {
                v[edge[i].to]=1;
                g[edge[i].to][k]=g[k][edge[i].to]=diss+1;
                h.push(Pair(diss+1,edge[i].to));
                maxl=max(maxl,diss+1);
            }
    }
}
void dij(int s)
{
    memset(v,0,sizeof(v));
    priority_queue<Pair,vector<Pair>,greater<Pair> > h;
    int dis[MAXN],maxx=0;for(int i=1;i<=n;i++) dis[i]=999999999;
    dis[s]=0;
    h.push(Pair(dis[s],s));
    while(h.size()>0)
    {
        int k=h.top().second;h.pop();
        if(v[k]) continue;
        v[k]=1;
        for(int i=head[k];i;i=edge[i].next)
        {
            if(dis[k]+edge[i].dis<dis[edge[i].to])
            {
                dis[edge[i].to]=dis[k]+edge[i].dis;
                h.push(Pair(dis[edge[i].to],edge[i].to));
            }
        }
    }
    queue<int> q;
    for(int i=1;i<=n;i++)
    if(dis[i]!=999999999) maxx=max(maxx,dis[i]);
    for(int i=1;i<=n;i++) if(dis[i]==maxx) q.push(i);
    if(maxx!=0)
        while(q.size()>0)
        {
            bfs(q.front(),maxx);q.pop();
        }
    else
    {
        for(int i=1;i<=n;i++)
        {
            bfs(i,maxx);
        }
    }
        printf("%d\n",maxx*100);
}
int main()
{

    while(scanf("%d%d",&n,&m)==2)
    {
        int maxl=0;
        if(m==0&&n==0) return 0;
        memset(edge,0,sizeof(edge));
        memset(g,0,sizeof(g));
        num=0;//memset(dis,0,sizeof(dis));
        memset(head,0,sizeof(head));
        for(int i=1;i<=m;i++)
        {
            int a,b;a=read();b=read();
            add(a,b,1);
            add(b,a,1);
        }
        dij(1);

    }
    return 0;
}

 

题材叙述

A国有N座城市,依次标为壹到N。同时,在那N座城池间有M条单向道路,每条道路的长度是2个正整数。现在,A国交通部钦赐了一条从城市壹到都市N的路径,并且保险那条路线的长短是兼备从城市1到城市N的门路中最短的。不幸的是,因为从城市一到都市N旅行的人更为多,那条由交通部钦赐的路子常常产生堵塞。今后A国想清楚,那条路子中的任意一条道路不可能通达时,由城市一到N的最短路径长度是有个别。

输入输出格式

输入格式:

 

输入文件首先行是八个用空格分开的正整数N、M和L,分别代表城市数量、单向道路数据和交通部钦赐的最短路径包涵多少条道路。按下来M行,每行三个用空格分开的整数a、b和c,表示存在一条由城市a到都市b的长短为c的单向道路。那M行的行号也是对应道路的号子,即内部第二行对应的征途编号为一,第一行对应的征途编号为2,…,第M行对应的征程编号为M。最终壹行为L个用空格分开的整数sp(一)…,,sp(L),依次表示从城市一到城池N的由交通部内定的最短路径上的道路的编号。

 

输出格式:

 

输出文件包罗L行,每行为贰个平头,第i行(i=一,二…,,L)的整数表示删去编号为sp(i)的道路后从城市一到城市N的最短路径长度。如若去掉后未有从城市1到城池N的路线,则输出11。

 

输入输出样例

输入样例#1:

4 5 2
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
1 5

出口样例#1:

6
6

说明

百分百的数量满足2<N<100000,1<M<200000。所用道路长度大于0小于10000。

 

题解:

玄学大火题,有如此三个结论:

去掉最短路上的一条边后,那么以后的最短路一定是
先沿原最短路走一段->再绕原非最短路走一端->再走回原最短路.

从而大家就足以初叶乱搞,从一上马枚举删除最短路上的边,然后用该边的左端点,在断掉该边后,去松弛原最短路上编号大于该点的点,

接下来答案正是f[u]+last[u]
(last[u]为u到n的最短路)
注意此题f数组不需求清空,然后我们就把f[u]+last[u]参预堆中,然后每一组通晓我们先删除非法的点(u在最短路上的编号小于当前面左端点编号),然后当前的堆顶就是答案,堆为空就是-一

 

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <queue>
 8 using namespace std;
 9 const int N=100005,M=200005;
10 int gi(){
11     int str=0;char ch=getchar();
12     while(ch>'9' || ch<'0')ch=getchar();
13     while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
14     return str;
15 }
16 int n,m,ps,num=0,head[N];
17 struct Lin{
18     int next,to,dis,id;
19 }a[M];
20 void init(int x,int y,int dis,int ids){
21     a[++num].next=head[x];a[num].to=y;a[num].dis=dis;a[num].id=ids;head[x]=num;
22 }
23 struct edge{
24     int x,y,dis;
25 }e[M];
26 struct node{
27     int id,dist;
28     bool operator <(const node &pp)const{
29         return dist>pp.dist;
30     }
31 };
32 priority_queue<node>st;
33 int last[N],imp[M],f[N],q[N*10],mod=N*10,id[N];bool vis[N],mark[N];
34 void spfa(int k)
35 {
36     memset(vis,0,sizeof(vis));
37     int t=0,sum=1,x,u;q[1]=e[k].x;vis[e[k].x]=true;
38     while(t!=sum){
39         t++;if(t==mod)t-=mod;x=q[t];
40         for(int i=head[x];i;i=a[i].next){
41             if(a[i].id==k)continue;
42             u=a[i].to;
43             if(f[x]+a[i].dis<f[u]){
44                 f[u]=a[i].dis+f[x];
45                 if(mark[u] && id[u]>id[e[k].x]){
46                     st.push((node){u,f[u]+last[u]});
47                 }
48                 if(!vis[u] && !mark[u]){
49                     vis[u]=true;
50                     sum++;if(sum==mod)sum-=mod;q[sum]=u;
51                 }
52             }
53         }
54         vis[x]=false;
55     }
56 }
57 void work()
58 {
59     n=gi();m=gi();ps=gi();
60     for(int i=1;i<=m;i++){
61         e[i].x=gi();e[i].y=gi();e[i].dis=gi();
62         init(e[i].x,e[i].y,e[i].dis,i);
63     }
64     for(int i=1;i<=ps;i++)imp[i]=gi(),id[e[imp[i]].y]=id[e[imp[i]].x]+1;
65     for(int i=ps;i>=1;i--){
66         last[e[imp[i]].x]=last[e[imp[i]].y]+e[imp[i]].dis;
67         mark[e[imp[i]].x]=true;mark[e[imp[i]].y]=true;
68     }
69     int x,y;
70     memset(f,127/3,sizeof(f));f[1]=0;
71     for(int i=1;i<=ps;i++){
72         x=e[i].x;y=e[i].y;
73         if(i>1)f[e[imp[i-1]].y]=f[e[imp[i-1]].x]+e[imp[i-1]].dis;
74         spfa(imp[i]);
75         while(!st.empty() && id[st.top().id]<=id[e[imp[i]].x])st.pop();
76         if(st.empty())printf("-1\n");
77         else{
78             printf("%d\n",st.top().dist);
79         }
80     }
81 }
82 int main()
83 {
84     work();
85     return 0;
86 }