当前位置: 代码迷 >> 综合 >> 洛谷 U5872 作弊
  详细解决方案

洛谷 U5872 作弊

热度:86   发布时间:2024-01-19 02:36:48.0

题目背景

现在是严肃的考场,kkk在认真的抄答案(雾)。

题目描述

考场里有N个人,其中有M对朋友关系,对于两个朋友,如果其中一个人x知道了答案,那么他一定会告诉另一个人y(如果y知道答案也一定会告诉x且花费时间相同),需要花费Time[x,y]。但是如果这个人自己都不知道答案,当然无法告诉另一个人咯。当然这N个人中也不乏自己独立做题的学霸。

输入输出格式

输入格式:

第一行两个整数N和M,意义如题所述。

接下来M行,每行三个整数x,y,Time[x,y]表示如果x知道了答案一定会和y说且耗时Time[x,y]。如果x=y说明这是个自己做题的学霸,做出来这题用了Time[x,x]

输出格式:

一个整数表示所有人都做出来这题的最小总时间。数据保证有解。

输入输出样例

输入样例#1:
3 3
1 1 1
1 2 2
2 3 3
输出样例#1:
6






说明

N<=2000

M<=13000

Time[][]<=20000

最后的解<=50000

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

并不知道这是什么算法……

原来以为是最短路,结果WA到飞起,后来看图神的改成了这种算法,按阶段算,真是厉害。


#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;int n,m,x,y,val,dis[2001][2001],minn,k,tot[2001],ans;
bool b[2001];int main()
{scanf("%d%d",&n,&m);memset(dis,0x3f,sizeof(dis));while(m--){scanf("%d%d%d",&x,&y,&val);dis[x][y]=min(dis[x][y],val);dis[y][x]=dis[x][y];}for(int i=1;i<=n;i++) tot[i]=dis[i][i];for(int i=1;i<=n;i++){minn=50005;k=-1;for(int j=1;j<=n;j++)if(!b[j] && tot[j]<minn){minn=tot[j];k=j;}b[k]=1;ans+=tot[k];for(int j=1;j<=n;j++)if(!b[j] && tot[j]>dis[j][k]) tot[j]=dis[j][k];}printf("%d\n",ans);return 0;
}


  相关解决方案