C. Anna, Svyatoslav and Maps

给定一个有向图,给定一条有向路径,求一条顶点最少的路径,使得给定的路径是它的最短路

folyd预处理出任意两点间的最短路,然后判断是否可以缩点

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
#define sc(x) scanf("%I64d",&(x));
#define rd(A) for(int i=0;i<N;i++) scanf("%I64d",&A[i]);
#define P pair<ll,ll>
#define se second
#define fi first
#define pb push_back
#define inf 1e18
#define endl '\n'
#define mem(A) memset(A,0,sizeof A);
#define maxn 1000+10
#define maxm 1000000+10
string A[maxn];
ll N,T,a,b,M;
ll B[maxm];
ll v[maxm];
ll dis[maxn][maxn];
void folyd(int n)
{
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
dis[i][j]=inf;
if(A[i][j-]=='')dis[i][j]=;
if(i==j)dis[i][j]=;
} } for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
for(int k=; k<=n; k++)
{
dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
}
}
} }
signed main()
{
sc(N);
for(int i=; i<=N; i++)
{
cin>>A[i];
}
sc(M);
folyd(N);
for(int i=; i<M; i++)
{
sc(B[i]);
}
int k=;
v[]=B[];
v[]=B[];
int pre=B[];
int p=B[];
for(int i=; i<M; i++)
{
//cout<<k<<' '<<i<<endl;
if(k>&&dis[pre][B[i]]>dis[pre][p])
{
//cout<<pre<<" "<<p<<" "<<i<<" "<<B[i]<<dis[pre][B[i]]<<' '<<dis[pre][p]<<endl;
k--;
pre=v[k-];
p=v[k];
}
//if(dis[pre][B[i]]<=dis[pre][p])
{
v[++k]=B[i];
pre=v[k-];
p=v[k];
} }
cout<<k+<<'\n';
for(int i=; i<=k; i++)
{
cout<<v[i]<<' ';
}
}

最新文章

  1. fdisk命令使用说明
  2. 字符串_KMP算法(求next[]模板 hdu 1711)
  3. 转:如何学习SQL(第一部分:SQL基础)
  4. [firefox+plug-n-hack]轻松地配置burpsuite代理https流量
  5. 【BZOJ】【1406】【AHOI2007】密码箱
  6. Application_Error
  7. LeetCode中有技巧的题需要面试前记得的
  8. git设置忽略某些文件或文件夹
  9. java.sql.SQLException:指定了无效的 Oracle URL
  10. 设置vim的默认工作路径同时与自动设当前编辑的文件所在目录为当前工作路径不冲突
  11. T9
  12. TRY
  13. Dynamics CRM2011 导入解决方案报根组件插入错误的解决方法
  14. 浅析数据结构中栈与C实现
  15. 关于Python2 与 Python3 的区别
  16. Asp.net Core 使用Jenkins + Dockor 实现持续集成、自动化部署(一):Jenkins安装
  17. linux中tomcat startup.sh出现commond not found
  18. noip第5课资料
  19. 关于Spring IOC (DI-依赖注入)需要知道的一切
  20. 不能从const char *转换为LPCWSTR --VS经常碰到

热门文章

  1. Python 内置函数super
  2. MySQL8 clone plugin
  3. CDQ分治总结
  4. CF和OF的区别
  5. PHP之简单工厂模式(二)
  6. DotNetCore知识栈
  7. C#设计模式:访问者模式(Vistor Pattern)
  8. STL之 stack
  9. mac chromedriver error
  10. vue filters过滤