SGU515：Recover path 【最短路】

警告：这题卡SPFA，警告：这题卡SPFA 这不是演习

题目大意：给出一个无向图，以及一些点的序列，要找出一条最短的路径使得通过所有点，题目保证存在一条头尾都在点的序列中的最短路满足题意

思路：没有最后那个保证应该就是神题了TUT 有的话显然最后的答案是一条链，而我们要做的便是找出这条链的头尾，随便找个序列中的点跑下最短路，那么头或尾两个点离这个点一定是最远的！找到一个端点后接下来便是DP找下一个端点，记忆化搜索使得路径上包含的序列点数最多，由于题目保证存在方案，最后这条路径一定是答案

最后。。。。这题卡SPFA 这不是演习

 #include <stdio.h>

 #include <iostream>

 #include<queue>

 #include <string.h>

 #include <algorithm>

 #define maxn 200009

 using namespace std;

 typedef pair<int,int>pii;

 int head[maxn],next[maxn],point[maxn],value[maxn],now=;

 int n,m,maxx=-,po,dist[maxn],x,y,z,k,v[maxn],dp[maxn],egz[maxn];

 int an=,pp[maxn],final[maxn],oo=;

 int num[maxn],route[maxn];

 void add(int x,int y,int v,int zz)

 {

     next[++now]=head[x];

     head[x]=now;

     point[now]=y;

     value[now]=v;

     num[now]=zz;

 }

 struct cmp

 {

     bool operator()(pii a,pii b)

     {

         return a.first>b.first;

     }

 };

 void dijkstra(int s)

 {

     memset(dist,-,sizeof(dist));

     dist[s]=;

     priority_queue<pii,vector<pii>,cmp>q;

     q.push(make_pair(,s));

     while(!q.empty())

     {

         pii u=q.top();

         q.pop();

         if(u.first>dist[u.second])continue;

         for(int i=head[u.second];i!=;i=next[i])

         {

             int k=point[i];

             if(dist[u.second]+value[i]<dist[k] || dist[k]==-)

             {

                 dist[k]=dist[u.second]+value[i];

                 q.push(make_pair(dist[k],k));

             }

         }

     }

 }

 /*

 void spfa(int s,int o)

 {

     int visit[maxn]={0};

     queue<int>q;

     for(int i=1;i<=n;i++)dist[i]=-1;

     dist[s]=0;

     visit[s]=1;

     q.push(s);

     while(!q.empty())

     {

         int u=q.front();

         q.pop();

         visit[u]=0;

         for(int i=head[u];i!=0;i=next[i])

         {

             int k=point[i];

             if(dist[u]+value[i]<dist[k]|| dist[k]==-1)

             {

                 dist[k]=dist[u]+value[i];

                 if(visit[k]==0)

                 {

                     visit[k]=1;

                     q.push(k);

                 }

             }

         }

     }

 }

 */

 int dfs(int s,int b)

 {

     if(dp[s]!=-)return dp[s];

     int ans=;

     for(int i=head[s];i!=;i=next[i])

     {

         int u=point[i];

         if(dist[u]!=dist[s]+value[i])continue;

         int val=dfs(u,(egz[s]?b+:b));

         if(val>ans)

         {

             ans=val;

             pp[s]=u;

             route[s]=num[i];

             if(val==k-)break;

         }

     }

     return dp[s]=ans+(egz[s]==?:);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

     {

         scanf("%d%d%d",&x,&y,&z);

         add(x,y,z,i);

         add(y,x,z,i);

     }

     scanf("%d",&k);

     for(int i=;i<=k;i++){scanf("%d",&v[i]);egz[v[i]]=;}

     dijkstra(v[]);

     for(int i=;i<=k;i++)if(dist[v[i]]>maxx)

     {

         maxx=dist[v[i]];

         po=v[i];

     }

     dijkstra(po);

     memset(dp,-,sizeof(dp));

     dfs(po,);

     an=po;

     while(pp[an]!=)

     {

         final[++oo]=route[an];

         an=pp[an];

     }

     printf("%d\n",oo);

     for(int i=;i<=oo-;i++)printf("%d ",final[i]);

     printf("%d",final[oo]);

     return ;

 }

巴特西

SGU515：Recover path 【最短路】

最新文章

热门文章