★★★   输入文件：route.in   输出文件：route.out   简单对比

时间限制：1 s   内存限制：128 MB

【问题描述】

    X城有一个含有N个节点的通信网络，在通信中，我们往往关心信息从一个节点I传输到节点J的最短路径。遗憾的是，由于种种原因，线路中总有一些节点会出故障，因此在传输中要避开故障节点。

任务一：在己知故障节点的情况下，求避开这些故障节点，从节点I到节点J的最短路径S0。

任务二：在不考虑故障节点的情况下，求从节点I到节点J的最短路径S1、第二最短路径S2。

【输入文件】

第1行： N I J (节点个数 起始节点 目标节点)

第2—N+1行： Sk1 Sk2…SkN (节点K到节点J的距离为SkJ K=1，2，……，N)

最后一行： P T1 T2……Tp (故障节点的个数及编号)

【输出文件】

S0 S1 S2 (S1<=S2 从节点I到节点J至少有两条不同路径)

【输入输出样例】

route.in

5 1 5

0 10 5 0 0

10 0 0 6 20

5 0 0 30 35

0 6 30 0 6

0 20 35 6 0

1 2

route.out

40 22 30

【约束条件】

(1)N<=50 N个节点的编号为1，2，…，N

(2)Skj为整数，Skj<=100，(K，J=1，2…，N 若Skj=0表示节点K到节点J没线路)

(3)P<=5 　

思路：先跑一个最短路再跑一个次短路，然后把有故障的点和与之相连的边删去，最后再跑一个最短路。

错因：题目中的路径为简单路，然而，我并没有考虑这一点。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 1000#define INF 0x3f3f3f3fusing namespace std;struct nond{    int g,f,to,vis[MAXN];    bool operator<(const nond &r) const {        if(r.f==f)    return r.g
          

que1; for(int i=0;i<=n;i++) dis[i]=INF; que1.push(s); vis[s]=1;dis[s]=0; while(!que1.empty()){ int now=que1.front(); que1.pop(); vis[now]=0; for(int i=head1[now];i;i=net1[i]) if(dis[to1[i]]>dis[now]+cap1[i]){ dis[to1[i]]=dis[now]+cap1[i]; if(!vis[to1[i]]){ vis[to1[i]]=1; que1.push(to1[i]); } } }}int Astar(int kk){ priority_queue

que; if(s==t) kk++; if(dis[s]==INF) return -1; tmp.g=0; tmp.to=s; tmp.f=dis[s]; que.push(tmp); while(!que.empty()){ tmp=que.top(); que.pop(); if(tmp.to==t) cnt++; if(cnt==kk) return tmp.g; for(int i=head[tmp.to];i;i=net[i]){ if(tmp.vis[to[i]]) continue; opt=tmp; opt.to=to[i]; opt.g=tmp.g+cap[i]; opt.f=opt.g+dis[to[i]]; opt.vis[to[i]]=1; que.push(opt); } } return -1;}int main(){ freopen("route.in","r",stdin); freopen("route.out","w",stdout); scanf("%d%d%d",&n,&s,&t); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ int x; scanf("%d",&x); map[i][j]=x; if(x!=0) add(i,j,x); } spfa(t); ans1=dis[s]; for(int i=2;i<=n;i++){ cnt=0; int bns=Astar(i); if(bns!=dis[s]){ ans2=bns; break; } } memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); memset(to1,0,sizeof(to1)); memset(cap1,0,sizeof(cap1)); memset(net1,0,sizeof(net1)); memset(head1,0,sizeof(head1)); tot1=0; scanf("%d",&p); for(int i=1;i<=p;i++){ int x; scanf("%d",&x); for(int j=1;j<=n;j++) map[x][j]=map[j][x]=0; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(map[i][j]) add(i,j,map[i][j]); spfa(t); ans3=dis[s]; printf("%d %d %d",ans3,ans1,ans2);}