题目背景
现在是严肃的考场,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;
}