zoj 3456 Traveler Nobita

zoj 3456 Traveler Nobita

#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;#define INF (1<<30)const int N=205;struct Edge{int u,v,w;Edge(){}Edge(int a,int b,int c) { u=a;v=b;w=c; }bool operator<(const Edge &b)const{return w<b.w;}};int n,m,fa[205];bool judge(int x){if(x%400==0) return true;if(x%4==0&&x%100!=0) return true;return false;}int find_fa(int x){if(fa[x]==x) return x;else return fa[x]=find_fa(fa[x]);}bool unin(int a,int b){int x=find_fa(a);int y=find_fa(b);if(x==y) return false;fa[x]=y; return true;}vector<Edge> edge;int MST(){for(int i=0;i<n;i++) fa[i]=i;int sum=0;sort(edge.begin(),edge.end());vector<Edge>::iterator it=edge.begin();while(it!=edge.end()){int u=it->u,v=it->v,w=it->w;if(!unin(u,v)) it=edge.erase(it);else {sum+=w;it++;}}for(int i=1;i<n;i++) if(find_fa(0)!=find_fa(i)) return INF;return sum;}int main(){while(scanf("%d%d",&n,&m)!=EOF){edge.clear();int valu[N]; for(int i=0;i<n;i++) {scanf("%d",&valu[i]);valu[i]*=24;}for(int i=0;i<m;i++){int a,b,c; scanf("%d%d%d",&a,&b,&c);edge.push_back(Edge(a,b,c*2+valu[a]+valu[b]));int hour=MST(),day=365;if(judge(1000+i)) day++;if(hour<=day*24) printf("%.2lfn",hour/24.0);else puts("-1");}puts("");}return 0;}