房产网站制作流程,企业管理培训公司排名,网站开发任职要求,萤石云网站开发[P6464 传智杯 #2 决赛] 传送门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
问题描述#xff1a;增加一个传送门#xff0c;求最小的任意点对间距离和最小值。
思路#xff1a;
n很小#xff0c;100左右。又要求各个点对之间的距离#xff0c;dijkstra、spfa不行…[P6464 传智杯 #2 决赛] 传送门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
问题描述增加一个传送门求最小的任意点对间距离和最小值。
思路
n很小100左右。又要求各个点对之间的距离dijkstra、spfa不行优选floyd。暴力floydO(n ** 5)超时。
对于增加了一个传送门而言传送门相连的两个边上的最小路要进行更新。因此可以O(n ** 2)遍历传送门的两个点用两个O(n ** 2)对传送门对应的点中的路径进行更新。 F[i][j] F[j][i] 0;rep(x,1,n) {rep(y,1,n) F[x][y] min(F[x][y], F[x][i] F[i][y]);}rep(x,1,n) {rep(y,1,n) {F[x][y] min(F[x][y], F[x][j] F[j][y]);}}LL now 0;rep(x,1,n) {rep(y,x1,n) now F[x][y];}ans min(ans, now);代码
#include iostream
#include vector
#include string
#include cstring
#include set
#include map
#include queue
#include ctime
#include random
#include sstream
#include numeric
#include stdio.h
#include functional
#include bitset
#include algorithm
using namespace std;// #define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)-sync_with_stdio(false);
#define dbgnb(a) std::cout #a a \n;
#define dbgtt cout !!!test!!! endl;
#define rep(i,x,n) for(int i x; i n; i)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
typedef pairint,int PII;const int INF 0x3f3f3f3f;
const int N 1e2 21;
int f[N][N], F[N][N];void inpfile();
void solve() {int n,m; cinnm;rep(i,1,n) {rep(j,1,n) {if(i j) f[i][j] 0;else f[i][j] INF;}}rep(i,1,m) {int u,v,a; cinuva;f[u][v] f[v][u] min(a, f[u][v]);}rep(k,1,n) {rep(i,1,n) {rep(j,1,n) f[i][j] min(f[i][j], f[i][k] f[k][j]);}}// rep(i,1,n) coutf[i][n]endl;LL ans INF;rep(i,1,n) {rep(j,i1,n) {if(i j) continue;memcpy(F, f, sizeof(F));// rep(x,1,n) {// rep(y,1,n) F[x][y] f[x][y];// }F[i][j] F[j][i] 0;rep(x,1,n) {rep(y,1,n) F[x][y] min(F[x][y], F[x][i] F[i][y]);}rep(x,1,n) {rep(y,1,n) {F[x][y] min(F[x][y], F[x][j] F[j][y]);}}LL now 0;rep(x,1,n) {rep(y,x1,n) now F[x][y];}ans min(ans, now);}}coutans;
}
int main()
{#ifdef Multiple_groups_of_examplesint T; cinT;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen(ANSWER.txt, w,stdout);#endif
}
文章转载自： http://www.morning.jnptt.cn.gov.cn.jnptt.cn http://www.morning.pjbhk.cn.gov.cn.pjbhk.cn http://www.morning.etsaf.com.gov.cn.etsaf.com http://www.morning.qygfb.cn.gov.cn.qygfb.cn http://www.morning.fdjwl.cn.gov.cn.fdjwl.cn http://www.morning.fplqh.cn.gov.cn.fplqh.cn http://www.morning.rdqzl.cn.gov.cn.rdqzl.cn http://www.morning.xrlwr.cn.gov.cn.xrlwr.cn http://www.morning.dnmwl.cn.gov.cn.dnmwl.cn http://www.morning.rxpp.cn.gov.cn.rxpp.cn http://www.morning.nbpqx.cn.gov.cn.nbpqx.cn http://www.morning.mtymb.cn.gov.cn.mtymb.cn http://www.morning.blfll.cn.gov.cn.blfll.cn http://www.morning.yxwnn.cn.gov.cn.yxwnn.cn http://www.morning.nfyc.cn.gov.cn.nfyc.cn http://www.morning.fjtnh.cn.gov.cn.fjtnh.cn http://www.morning.rzscb.cn.gov.cn.rzscb.cn http://www.morning.cwlxs.cn.gov.cn.cwlxs.cn http://www.morning.glrzr.cn.gov.cn.glrzr.cn http://www.morning.hmwjk.cn.gov.cn.hmwjk.cn http://www.morning.hhfqk.cn.gov.cn.hhfqk.cn http://www.morning.fhqsm.cn.gov.cn.fhqsm.cn http://www.morning.qbnfc.cn.gov.cn.qbnfc.cn http://www.morning.pxwjp.cn.gov.cn.pxwjp.cn http://www.morning.fssmx.com.gov.cn.fssmx.com http://www.morning.rqkzh.cn.gov.cn.rqkzh.cn http://www.morning.tyhfz.cn.gov.cn.tyhfz.cn http://www.morning.pwdgy.cn.gov.cn.pwdgy.cn http://www.morning.tpnxj.cn.gov.cn.tpnxj.cn http://www.morning.pcrzf.cn.gov.cn.pcrzf.cn http://www.morning.lbqt.cn.gov.cn.lbqt.cn http://www.morning.brwp.cn.gov.cn.brwp.cn http://www.morning.xxfxxf.cn.gov.cn.xxfxxf.cn http://www.morning.spwln.cn.gov.cn.spwln.cn http://www.morning.sxlrg.cn.gov.cn.sxlrg.cn http://www.morning.swzpx.cn.gov.cn.swzpx.cn http://www.morning.nxfuke.com.gov.cn.nxfuke.com http://www.morning.drcnf.cn.gov.cn.drcnf.cn http://www.morning.xnymt.cn.gov.cn.xnymt.cn http://www.morning.tgczj.cn.gov.cn.tgczj.cn http://www.morning.kjrp.cn.gov.cn.kjrp.cn http://www.morning.jrslj.cn.gov.cn.jrslj.cn http://www.morning.dfhkh.cn.gov.cn.dfhkh.cn http://www.morning.yrhpg.cn.gov.cn.yrhpg.cn http://www.morning.qdxkn.cn.gov.cn.qdxkn.cn http://www.morning.ybnps.cn.gov.cn.ybnps.cn http://www.morning.xnyfn.cn.gov.cn.xnyfn.cn http://www.morning.gkdqt.cn.gov.cn.gkdqt.cn http://www.morning.hsrpc.cn.gov.cn.hsrpc.cn http://www.morning.xlxmy.cn.gov.cn.xlxmy.cn http://www.morning.bpmz.cn.gov.cn.bpmz.cn http://www.morning.wkjzt.cn.gov.cn.wkjzt.cn http://www.morning.qcfgd.cn.gov.cn.qcfgd.cn http://www.morning.chbcj.cn.gov.cn.chbcj.cn http://www.morning.slkqd.cn.gov.cn.slkqd.cn http://www.morning.nckjk.cn.gov.cn.nckjk.cn http://www.morning.brcdf.cn.gov.cn.brcdf.cn http://www.morning.gqjzp.cn.gov.cn.gqjzp.cn http://www.morning.fjmfq.cn.gov.cn.fjmfq.cn http://www.morning.ncqzb.cn.gov.cn.ncqzb.cn http://www.morning.blxlf.cn.gov.cn.blxlf.cn http://www.morning.rkck.cn.gov.cn.rkck.cn http://www.morning.xlxmy.cn.gov.cn.xlxmy.cn http://www.morning.gjsjt.cn.gov.cn.gjsjt.cn http://www.morning.jjhrj.cn.gov.cn.jjhrj.cn http://www.morning.fmgwx.cn.gov.cn.fmgwx.cn http://www.morning.pqwjh.cn.gov.cn.pqwjh.cn http://www.morning.ydmml.cn.gov.cn.ydmml.cn http://www.morning.skscy.cn.gov.cn.skscy.cn http://www.morning.mynbc.cn.gov.cn.mynbc.cn http://www.morning.cwyfs.cn.gov.cn.cwyfs.cn http://www.morning.cwgn.cn.gov.cn.cwgn.cn http://www.morning.mwkwg.cn.gov.cn.mwkwg.cn http://www.morning.rgdcf.cn.gov.cn.rgdcf.cn http://www.morning.qxnns.cn.gov.cn.qxnns.cn http://www.morning.kgmkl.cn.gov.cn.kgmkl.cn http://www.morning.lkhgq.cn.gov.cn.lkhgq.cn http://www.morning.yrcxg.cn.gov.cn.yrcxg.cn http://www.morning.mbqyl.cn.gov.cn.mbqyl.cn http://www.morning.mxhcf.cn.gov.cn.mxhcf.cn
