P1078 文化之旅

小咪咪 2021-11-26 07:28 376阅读 0赞

[题目][Link 1]

# 代码 #

#include<iostream> #include<cstdio> #include<queue> using namespace std; int n,k,m,s,t,g[105][105],head[105],Next[10005],adj[10005],ti[10005],p,i,j,cul[105],f[105][105],u,v,w,ans=1<<30,vis[105]; void Push(int u,int v,int w) { Next[++p]=head[u]; head[u]=p; adj[p]=v; ti[p]=w; } void dfs(int i,int s) { int j,k,flag=0; if(s+f[i][t]>ans) return; if(i==t) { ans=s; return; } vis[++p]=cul[i]; for(j=head[i];j!=0;j=Next[j]) { flag=1; for(k=1;k<=p;k++) if(vis[k]==cul[adj[j]]||g[cul[adj[j]]][vis[k]]==1) flag=0; if(flag) dfs(adj[j],s+ti[j]); } p--; } int main(){ scanf("%d %d %d %d %d",&n,&k,&m,&s,&t); for(i=1;i<=n;i++) scanf("%d",&cul[i]); for(i=1;i<=k;i++) for(j=1;j<=k;j++) scanf("%d",&g[i][j]); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) f[i][j]=1<<29; f[i][i]=0; } for(i=1;i<=m;i++) { scanf("%d %d %d",&u,&v,&w); if(g[cul[v]][cul[u]]==0&&cul[u]!=cul[v]) { Push(u,v,w); f[u][v]=w; } } for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(p=1;p<=n;p++) f[i][j]=min(f[i][j],f[i][p]+f[p][j]); p=0; if(f[s][t]!=1<<29) printf("%d",f[s][t]); else printf("-1"); }

此题复制有乱码，于是贴了链接。

转载于:https://www.cnblogs.com/xiongchongwen/p/11137590.html

[Link 1]: https://www.luogu.org/problemnew/show/P1078

发表评论取消回复

表情：

评论列表（有 0 条评论，376人围观）

还没有评论，来说两句吧...

相关阅读

相关 1078. Bigram 分词

给出第一个词 `first` 和第二个词 `second`，考虑在某些文本 `text` 中可能以 "`first second third`" 形式出现的情况，其中 `sec

╰+哭是因爲堅強的太久メ/ 2023年10月04日 08:24/ 0 赞/ 105 阅读

相关 Hugo 之旅

![format_png][] 之前写了篇文章《博客迁移至 Hugo》\[1\]，提了下使用 Typecho 多年后越发感受到运维的成本之高后，将博客迁移到了静态博客程序 H

心已赠人/ 2022年12月20日 02:40/ 0 赞/ 436 阅读

相关 Vijos P1964夜夜的NOIP之旅

P1964夜夜的NOIP之旅 [Accepted][] 标签： \[显示标签\] 背景有些人出题十分的不靠谱说好的NOIP难度呢? 说好的NOI

╰半夏微凉°/ 2022年08月20日 03:23/ 0 赞/ 117 阅读

相关 Ural 1078 segement

O(n^2)的动态规划的算法。 include <cstdio> include <cstring> include <cstdlib> in

爱被打了一巴掌/ 2022年08月11日 06:29/ 0 赞/ 250 阅读

相关 P - FatMouse and Cheese HDU - 1078——dfs+记忆化搜索

Think: 1知识点：dfs+记忆化搜索 2题意：输入一个邻接矩阵，求一条递增路径，满足沿四个方向直线移动最多k步的条件，使得路径经过的点权之和最大 [vjudge

柔情只为你懂/ 2022年06月10日 03:59/ 0 赞/ 281 阅读

相关 1078. Hashing (25)

The task of this problem is simple: insert a sequence of distinct positive integers into

红太狼/ 2022年05月29日 13:25/ 0 赞/ 229 阅读

相关 jvm之旅

一、jvm的简介 jvm是运行java语言的一个环境，就是常说的jdk或者jre，但是我们要区分这三个概念，其中jvm是运行java的环境，而jre是在jvm

阳光穿透心脏的1/2处/ 2022年05月28日 07:49/ 0 赞/ 322 阅读

相关 PAT A1078

![clipboard.png][] 这道题牵扯到了hash散列中的集中查询方式，随后做一个总结，对于素数方面，没有神马难度； include<iostream>

以你之姓@/ 2022年03月07日 00:20/ 0 赞/ 259 阅读

相关 P1078 文化之旅

[题目][Link 1] 代码 include<iostream> include<cstdio> include<queue> using namespace

小咪咪/ 2021年11月26日 07:28/ 0 赞/ 377 阅读

相关文化之旅

题目描述有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不

布满荆棘的人生/ 2021年11月17日 15:01/ 0 赞/ 514 阅读