Moderator: Board moderators
Well,If you find several solutions, output only one of them.
Code: Select all
The last domino falls after 7.5 seconds, between key dominoes 2 and 3.Code: Select all
The last domino falls after 7.5 seconds, between key dominoes 3 and 2.
.
Code: Select all
//My code
#include<iostream>
#include<vector>
#include<set>
using namespace std;
long mat[500][500];
vector<int> v[500];
int n,m;
long dist[500];
//int parent[500];
void get(){
memset(dist , -1 , sizeof dist);
//memset(parent , -1 , sizeof parent);
set<pair<long , int> > q;
q.insert(make_pair(0 ,0 ));
dist[0] = 0;
while(!q.empty()){
pair<long , int> p = *q.begin(); q.erase(q.begin());
int i = p.second;
for(int k = 0 ; k<(signed int)v[p.second].size() ; k++){
int j = v[p.second][k];
long c = p.first + mat[i][j];
if(dist[j]==-1 || c<dist[j]){
dist[j] = c;
//parent[j] = i;
q.insert(make_pair(c , j));
}
}
}
}
int main(){
freopen("1.in" , "rt" , stdin);
int t = 0;
while(true){
cin>>n>>m;
if(!n&&!m) break;
t++;
printf("System #%d\n",t);
memset(mat , -1 , sizeof mat);
for(int i = 0 ; i<500 ; i++)
v[i].clear();
for(int i = 0 ; i<m ; i++){
int x , y ;
long l;
cin>>x>>y>>l;
x--;
y--;
mat[x][y] = mat[y][x] = l;
v[x].push_back(y);
v[y].push_back(x);
}
get();
printf("The last domino falls after ");
vector<pair<double , pair<int , int> > > vv;
for(int i = 0 ; i<n ; i++){
if(dist[i]==-1) continue;
vv.push_back(make_pair(-dist[i] , make_pair(-1 , i)));
}
for(int i = 0 ; i<n ; i++){
for(int j = i+1 ; j<n;j++){
if(mat[i][j]==-1) continue;
if((dist[i]<=dist[j] && dist[i]+mat[i][j]<= dist[j]) || (dist[j]<dist[i] && dist[j]+mat[j][i]<=dist[i])) continue;
double d = (dist[i]+dist[j]+mat[i][j])/2.0;
vv.push_back(make_pair(-d , make_pair(i , j)));
}
}
sort(vv.begin() , vv.end());
pair<double , pair<int , int> > pp = vv[0];
if(pp.second.first==-1){
printf("%.1lf seconds, at key domino %d.\n\n" ,(double)-pp.first , pp.second.second+1 );
}else{
printf("%.1lf seconds, between key dominoes %d and %d.\n\n" ,(double)-pp.first , pp.second.first+1 , pp.second.second+1 );
}
}
}
Code: Select all
#include <cstdio>
#include <queue>
using namespace std;
struct Domino
{
int id;
int time;
bool in_Queue;
bool fresh;
};
struct Row
{
int length;
bool exists;
};
int main()
{
queue<struct Domino *> Q;
struct Domino dominoes[502];
Row matrix[502][502];
int n, m;
int a, b, l;
bool case_A=false, case_B=false;
double last=0.0;
int d1, d2;
int counter=0;
for(int i=0;i<502;i++)
{
dominoes[i].id=i;
}
while(1)
{
scanf("%d %d",&n,&m);
if(n==0 && m==0)
break;
for(int i=0;i<=n;i++)
{
dominoes[i].fresh=true;
dominoes[i].in_Queue=false;
dominoes[i].time=0;
}
for(int i=0;i<502;i++)
{
for(int j=0;j<502;j++)
{
matrix[i][j].exists=false;
}
}
for(int i=0;i<m;i++)
{
scanf("%d %d %d",&a, &b, &l);
a--; b--;
matrix[a][b].exists=true;
matrix[a][b].length=l;
matrix[b][a].exists=true;
matrix[b][a].length=l;
}
dominoes[0].fresh=false;
dominoes[0].in_Queue=true;
dominoes[0].time=0;
Q.push(&dominoes[0]);
last=0.0;
while(!Q.empty())
{
struct Domino *D_ptr;
D_ptr=Q.front(); Q.pop();
for(int i=0;i<n;i++)
{
if(matrix[D_ptr->id][i].exists)
{
if(dominoes[i].fresh)
{
dominoes[i].fresh=false; dominoes[i].in_Queue=true;
dominoes[i].time=D_ptr->time+matrix[D_ptr->id][i].length;
if((double)(dominoes[i].time) > last)
{
last=(double)(dominoes[i].time); d1=i; case_A=true; case_B=false;
}
Q.push(&dominoes[i]);
continue;
}
if(D_ptr->time==dominoes[i].time)
{
if(((double)matrix[D_ptr->id][i].length/2.0+(double)(D_ptr->time)) > last )
{
case_A=false; case_B=true; last=(double)matrix[D_ptr->id][i].length/2.0+(double)D_ptr->time;
if(i< (D_ptr->id ))
{
d1=i; d2=D_ptr->id;
}
else
{
d1=D_ptr->id; d2=i;
}
}
}
if((dominoes[i].time) > (D_ptr->time))
{
if((dominoes[i].time)> (matrix[D_ptr->id][i].length +D_ptr->time ) )
{
dominoes[i].time=matrix[D_ptr->id][i].length +D_ptr->time;
if(dominoes[i].in_Queue==false)
{
Q.push(&dominoes[i]);
dominoes[i].in_Queue=true;
}
continue;
}
if((dominoes[i].time) == (matrix[D_ptr->id][i].length +D_ptr->time ) )
{
continue;
}
if((double(dominoes[i].time)+double(matrix[D_ptr->id][i].length-(dominoes[i].time-D_ptr->time))/2.0)>last)
{
last=(double(dominoes[i].time)+double( matrix[D_ptr->id][i].length-(dominoes[i].time-D_ptr->time))/2.0);
case_B=true; case_A=false;
if(i< (D_ptr->id ))
{
d1=i; d2=D_ptr->id;
}
else
{
d1=D_ptr->id; d2=i;
}
}
}
if((D_ptr->time) > dominoes[i].time)
{
if((dominoes[i].time+matrix[D_ptr->id][i].length) < D_ptr->time)
{
D_ptr->time=dominoes[i].time+matrix[D_ptr->id][i].length;
i=-1;
continue;
}
if((dominoes[i].time+matrix[D_ptr->id][i].length) == D_ptr->time)
{
continue;
}
if( ( double(matrix[D_ptr->id][i].length-(D_ptr->time-dominoes[i].time))/2.0 + double(D_ptr->time) ) >last )
{
last= double(matrix[D_ptr->id][i].length-(D_ptr->time-dominoes[i].time))/2.0 + double(D_ptr->time);
case_B=true; case_A=false;
if(i< (D_ptr->id ))
{
d1=i; d2=D_ptr->id;
}
else
{
d1=D_ptr->id; d2=i;
}
}
}
}
}
D_ptr->in_Queue=false;
}
counter++;
if(counter>=2)
{
printf("\n");
}
if(case_A)
{
printf("System #%d\n",counter);
printf("The last domino falls after %.1lf seconds, at key domino %d.\n",last,d1 + 1);
}
else if(case_B)
{
printf("System #%d\n",counter);
printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n",last,d1+1,d2+1);
}
}
return 0;
}
Code: Select all
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader vhod = new BufferedReader(new InputStreamReader(System.in));
int n;
int m;
Graf g;
int[] vr;
int[] cas;
String[] s;
int[] resitev;
int t;
int t0;
for(int j=1;true;j++){
s= vhod.readLine().trim().split(" ");
n=Integer.parseInt(s[0]);
m=Integer.parseInt(s[1]);
if(n==0&&m==0){
//System.out.println();
break;
}
g= new Graf(n,m);
for(int i=0;i<n;i++){
g.dodajTocko();//pazit - oznake tock so za 1 manj!!
}
vr=new int[m];
for(int i=0;i<m;i++){
s=vhod.readLine().split(" ");
//System.out.println(g.tocke.length);
g.dodajPovezavo(g.tocke[Integer.parseInt(s[0])-1], g.tocke[Integer.parseInt(s[1])-1]);//oznake povezav so za eno manj!
vr[i]=Integer.parseInt(s[2]);
}
//tu so podatki prebrani
cas=dijkstra(g,vr,g.tocke[0]);
/*for(int i=0;i<cas.length;i++){
System.out.println(cas[i]);
}*/
//sedaj vemo, kdaj se posamezne kljucne domine podrejo.
resitev = new int[3];//med katerima kljucnima dominama in kdaj se podre zadnja domina
resitev[0]=-1;
resitev[1]=-1;//zacetna to?ka je namrec 1 in se podre sama! - v casu 0
resitev[2]=0;
for(int i=0;i<m;i++){
t0=Math.abs(cas[g.povezave[i].konec.nasprotna.oznaka]-cas[g.povezave[i].zacetek.nasprotna.oznaka]);//V kolikem casovnem intervalu padeta sosednji domini
t=cas[g.povezave[i].konec.nasprotna.oznaka]+cas[g.povezave[i].zacetek.nasprotna.oznaka]+vr[i];//dvakratni cas, ki potece, da pade povezava (po krajsem racunu) - dvakratni zato, da lahko delamo s celinmi stevili
if(t>=resitev[2]){//Tu se alternativa - lahko >=! TODO
if(t0==vr[i]){//ce se pred podrtjem enega izmed krajisc podre cela povezava - konec je v kljucni domini
resitev[0]=resitev[1]=-1-((cas[g.povezave[i].konec.nasprotna.oznaka]>cas[g.povezave[i].zacetek.nasprotna.oznaka])? g.povezave[i].konec.nasprotna.oznaka : g.povezave[i].zacetek.nasprotna.oznaka);// z minus smo ozna?ili zato, da bomo vedeli, da je konec v vozliš?u!
resitev[2]=t;
continue;
}
if(t==resitev[2])continue;//ta if je le zaradi morebitne muhavosti serverja UVa
//naslednji if je le zato, da bosta tocki urejeni po casu narascajoce, nato po indeksu. Verjetno ni potreben.
if(cas[g.povezave[i].konec.nasprotna.oznaka]<cas[g.povezave[i].zacetek.nasprotna.oznaka]||(cas[g.povezave[i].konec.nasprotna.oznaka]==cas[g.povezave[i].zacetek.nasprotna.oznaka])&&g.povezave[i].konec.nasprotna.oznaka<g.povezave[i].zacetek.nasprotna.oznaka){
resitev[0]=1+g.povezave[i].konec.nasprotna.oznaka;
resitev[1]=1+g.povezave[i].zacetek.nasprotna.oznaka;
}
else{
resitev[1]=1+g.povezave[i].konec.nasprotna.oznaka;
resitev[0]=1+g.povezave[i].zacetek.nasprotna.oznaka;
}
resitev[2]=t;
}
}
//sedaj moramo samo se izpisati resitev
System.out.println("System #"+j);
//g.izpis();
System.out.println("The last domino falls after "+resitev[2]/2+"."+5*(resitev[2]%2)+ " seconds, "+(resitev[0]<=0? "at key domino "+(-resitev[0])+"." : "between key dominoes "+resitev[0]+" and "+resitev[1]+"."));
System.out.println();
}
}
public static int[] dijkstra(Graf g, int[] vr, Tocka t)
{
boolean[] obisk = new boolean[g.n];
Povezava[] min = new Povezava[g.n];//minimalne povezave do povezanega dela
//Povezava[] drevo = new Povezava[g.n];//koncne povezave - tega ne rabimo*********
int[] vrednosti = new int[g.n];//kdaj bo katera izmed kljucnih domin padla
obisk[t.oznaka] = true;
vrednosti[t.oznaka] = 0;
//drevo[t.oznaka] = null; //gre ven*************************
Tocka u,v;
Povezava e;
for (Stik s = t.sosedje; s != null; s = s.naslednji) {
v = s.nasprotna;
if(v==t)continue;
e = s.povezava;
min[v.oznaka] = e;//////preglej!
//Tu zbrisal pogoj: if (min[v.oznaka] == null || vr[e.oznaka] < vr[min[v.oznaka].oznaka])
}// s tem smo oznacili minimalne povezave do povezanega dela (zacetne tocke)
while (true) {
e=null;
//domina u bo v naslednjem koraku po povezavi e "podrla" domino v
for (int i = 0; i < g.n; ++i) {//po vozliscih iscemo naslednjo povezavo med povezanim in nepovezanim delom
if (obisk[i]) continue;
if (min[i] == null) continue;
if (e == null) e = min[i];
else {
//j=nasprotna tocka od i povezave min[i]
//k=nasprotna tocka od i povezave e
int j = (min[i].konec.nasprotna.oznaka == i) ? min[i].zacetek.nasprotna.oznaka : min[i].konec.nasprotna.oznaka;
int k = (e.konec.nasprotna.oznaka == i) ? e.zacetek.nasprotna.oznaka : e.konec.nasprotna.oznaka;
if (vrednosti[j] + vr[min[i].oznaka] < vrednosti[k] + vr[e.oznaka]) e = min[i];
}
}
if (e == null) break;//tu zakljucimo z while zanko! Smo povezali vse!
if (obisk[e.konec.nasprotna.oznaka]) {
v = e.zacetek.nasprotna;
u = e.konec.nasprotna;
}
else {
v = e.konec.nasprotna;
u = e.zacetek.nasprotna;
}
//do tod smo nasli, katera kljucna domina bo podrta naslednja: v (iz u)
obisk[v.oznaka] = true;
vrednosti[v.oznaka] = vrednosti[u.oznaka] + vr[e.oznaka];//kdaj bo podrta domina v
//drevo[v.oznaka] = e;//************************************
//sedaj na novo nastavimo tabelo "minimalnih poti" iz nepovezanega dela
for (Stik s = v.sosedje; s != null; s = s.naslednji) {
u = s.nasprotna;
if(obisk[u.oznaka])continue;//to dodal!
e = s.povezava;
if (min[u.oznaka] == null) min[u.oznaka] = e;
else {
//j=oznaka nasprotne tocke od u (t.j. od "nove" tocke, od katere smo prisli)
//k=oznaka tiste tocke iz povezanega dela, ki je bila od u do zdaj najmanj oddaljena.
//stara koda: int j = (e.konec.nasprotna.oznaka == u.oznaka) ? e.zacetek.nasprotna.oznaka : e.konec.nasprotna.oznaka;
int j=v.oznaka;
int k = (min[u.oznaka].konec.nasprotna.oznaka == u.oznaka) ? min[u.oznaka].zacetek.nasprotna.oznaka : min[u.oznaka].konec.nasprotna.oznaka;
if (vrednosti[j] + vr[e.oznaka] < vrednosti[k] + vr[min[u.oznaka].oznaka]) min[u.oznaka] = e;
}
}
}
//return drevo;
return vrednosti;
}
}
class Graf
{
Tocka[] tocke;
Povezava[] povezave;
int n; // stevilo tock
int m; // stevilo povezav
public Graf(int maxn, int maxm)
{
tocke = new Tocka[maxn];
povezave = new Povezava[maxm];
n = 0;
m = 0;
}
public Tocka dodajTocko()
{
tocke[n] = new Tocka(n);
return tocke[n++];
}
public Povezava dodajPovezavo(Tocka z, Tocka k)
{
povezave[m] = new Povezava(z, k, m);
return povezave[m++];
}
public void odstraniTocko(Tocka t)
{
while (t.sosedje != null) odstraniPovezavo(t.sosedje.povezava);
if (t.oznaka < n - 1) {
tocke[t.oznaka] = tocke[n - 1];
tocke[t.oznaka].oznaka = t.oznaka;
}
tocke[--n] = null;
}
public void odstraniPovezavo(Povezava p)
{
Tocka z = p.konec.nasprotna; // kazalec na zacetno tocko
Tocka k = p.zacetek.nasprotna; // kazalec na koncno tocko
if (p.zacetek == z.sosedje) z.sosedje = p.zacetek.naslednji;
else {
Stik stevec = z.sosedje;
while (stevec.naslednji != p.zacetek) stevec = stevec.naslednji;
stevec.naslednji = p.zacetek.naslednji;
}
if (p.konec == k.sosedje) k.sosedje = p.konec.naslednji;
else {
Stik stevec = k.sosedje;
while (stevec.naslednji != p.konec) stevec = stevec.naslednji;
stevec.naslednji = p.konec.naslednji;
}
if (p.oznaka < m - 1) {
povezave[p.oznaka] = povezave[m - 1];
povezave[p.oznaka].oznaka = p.oznaka;
}
povezave[--m] = null;
}
public void izpis() // izpise sosede vsake tocke
{
for (int i = 0; i < n; ++i) {
System.out.print(i + ":");
for (Stik s = tocke[i].sosedje; s != null; s = s.naslednji)
System.out.print(" " + s.nasprotna.oznaka);
System.out.println();
}
}
public static Graf petersen(int n, int k)
{
Graf g = new Graf(2 * n, 3 * n);
for (int i = 0; i < 2 * n; ++i) g.dodajTocko();
for (int i = 0; i < n; ++i) {
g.dodajPovezavo(g.tocke[i], g.tocke[n + i]);
g.dodajPovezavo(g.tocke[i], g.tocke[(i + 1) % n]);
g.dodajPovezavo(g.tocke[n + i], g.tocke[n + (i + k) % n]);
}
return g;
}
public Tocka[] pregledVSirino(Tocka t)
{
Tocka[] vrsta = new Tocka[n];
boolean[] obiskana = new boolean[n];
int i = 0;
int j = 0;
vrsta[i++] = t;
obiskana[t.oznaka] = true;
while (j < i) {
t = vrsta[j++];
for (Stik s = t.sosedje; s != null; s = s.naslednji) {
Tocka u = s.nasprotna;
if (!obiskana[u.oznaka]) {
vrsta[i++] = u;
obiskana[u.oznaka] = true;
}
}
}
return vrsta;
}
}
class Tocka
{
Stik sosedje;
int oznaka;
public Tocka(int i)
{
oznaka = i;
sosedje = null;
}
public int stopnja()
{
int i = 0;
for (Stik s = sosedje; s != null; s = s.naslednji) ++i;
return i;
}
}
class Povezava
{
Stik zacetek;
Stik konec;
int oznaka;
public Povezava(Tocka z, Tocka k, int i)
{
zacetek = new Stik(k,this);
zacetek.naslednji = z.sosedje;
z.sosedje = zacetek;
konec = new Stik(z, this);
konec.naslednji = k.sosedje;
k.sosedje = konec;
oznaka = i;
}
public String toString()
{
return konec.nasprotna.oznaka + ", " + zacetek.nasprotna.oznaka;
}
}
class Stik
{
Tocka nasprotna;
Povezava povezava;
Stik naslednji;
public Stik(Tocka t, Povezava p)
{
nasprotna = t;
povezava = p;
naslednji = null;
}
}
Code: Select all
#include <stdio.h>
#include <stdlib.h>
int rt_c;
int row[501][501];
int d[501];
int S[501];
double row_time[501][501];/*time when each row down*/
void relax(int,int);
void down(int,int);
int find_min(int);
int main(){
int n,m,N=1;
int i,j,k,l;
double Max;
int ver;
int key;
int p1,p2;
/*freopen("318.in","r",stdin);
freopen("out.out","w",stdout);*/
scanf("%d",&n);
scanf("%d",&m);
while(!(0==n&&0==m)){
if(N>=2)
printf("\n");
rt_c=0;
for(k=1;k<=n;k++){
S[k] = 0;
d[k] = -1;
for(j=1;j<=n;j++){
row[k][j] = -1;
row_time[k][j] = -1;
}
}
/*initial*/
for(k=0;k<m;k++){
scanf("%d",&i);
scanf("%d",&j);
scanf("%d",&row[i][j]);
row[j][i] = row[i][j];
}
/*read input*/
d[1] = 0;
for(i=1;i<=n;i++){
k = find_min(n);
if(S[k]!=1){
S[k]=1;
for(j=1;j<=n;j++){
if(row[k][j]!=(-1))
relax(k,j);
}
}
}
/*run Dijkstra's algorithm to get the time key domino down*/
for(i=1;i<n;i++){
for(j=i+1;j<=n;j++){
if(row[i][j]>=0)
down(i,j);
}
}
/*get the time each row down*/
Max = -1;
ver = 0; /*if ver = 0 output key domino*/
for(i=1;i<=n;i++){
if(d[i] > Max){
key = i;
Max=d[i];
}
}
/*find max for key and row*/
for(i=1;i<n;i++){
for(j=i+1;j<=n;j++){
if(row_time[i][j] > Max){
Max = row_time[i][j];
p1=i;
p2=j;
ver=1;
}
}
}
printf("System #%d\n",N);
printf("The last domino falls after %.1lf seconds, ",Max);
if(ver==0)
printf("at key domino %d.\n",key);
else
printf("between key dominoes %d and %d.\n",p1,p2);
scanf("%d",&n);
scanf("%d",&m);
N++;
}
return 0;
}
void relax(int u,int v){
if (d[v]>d[u]+row[u][v] || d[v]==-1)
d[v] = d[u] + row[u][v];
}
void down(int u,int v){
int i,j;
double tmp1,tmp2,tmp3;
if(d[u] > d[v]){
i = d[u];
j = d[v];
}else{
i = d[v];
j = d[u];
}
if(i-j == row[u][v])
row_time[u][v] = i;
else{
tmp1 = i-j;
tmp2 = j;
tmp3 = row[u][v];
row_time[u][v] = (i+j+tmp3)/2;
}
rt_c++;
}
int find_min(int n){
int i,min,min_i,co;
co = 0;
for(i=1;i<=n;i++){
if(S[i]!=1 && d[i]!=(-1)){
if(0 == co){
co = 1;
min = d[i];
min_i = i;
}else{
if(d[i]<min){
min = d[i];
min_i = i;
}
}
}
}
return min_i;
}
Code: Select all
1 0
getting wa again and again..what's wrong in my code??somebody pls help...
Code: Select all
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define pb push_back
#define loop(i,a,b) for (i=a;i<=b;i++)
#define maxm 501
using namespace std;
long long color[maxm],timee[maxm],mark[maxm];
vector< long long > g[maxm],cost[maxm];
long long r,s,z;
void dfs(long long a)
{
color[a]=1;
long long m=g[a].size(),i;
loop(i,0,m-1)
{
long long v=g[a][i];
if (!color[v])
{
r=a;s=v;
z=cost[a][i];
timee[v]=timee[a]+z;
dfs(v);
}
else mark[v]=1;
}
}
int main()
{
long long domino_numb,i,j,k,rows,m,n;
long long casee=1;
while(scanf("%lld%lld",&domino_numb,&rows)==2 && domino_numb)
{
loop(i,1,domino_numb) {color[i]=0;mark[i]=0;}
long long domino_1,domino_2,t;
while(rows--)
{
scanf("%lld%lld%lld",&domino_1,&domino_2,&t);
g[domino_1].push_back(domino_2);
g[domino_2].push_back(domino_1);
cost[domino_2].pb(t);
cost[domino_1].pb(t);
}
s=1;z=0;
timee[1]=0;
dfs(1);
double falling_timee=timee[s];
printf("System #%lld\n",casee++);
if (mark[s])
{
falling_timee-=(z/2.0);
if (r>s) {long long temp=r;r=s;s=temp;}
printf("The last domino falls after %.1lf seconds, between key dominoes %lld and %lld.\n",falling_timee,r,s);
}
else
printf("The last domino falls after %.1lf seconds, at key domino %lld.\n",falling_timee,s);
loop(i,1,domino_numb) {g[i].clear();cost[i].clear();}
puts("");
}
return 0;
}
Code: Select all
3 3
1 2 5
1 3 10
2 3 5
0 0
Code: Select all
System #1
The last domino falls after 10.0 seconds, at key domino 3.
Code: Select all
#include<bits/stdc++.h>
#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define sc4(w,x,y,z) scanf("%d%d%d%d",&w,&x,&y,&z)
#define pr(x) printf("%d",x)
#define pr2(x,y) printf("%d %d",x,y)
#define pr3(x,y,z) printf("%d %d %d",x,y,z)
#define pr4(w,x,y,z) printf("%d %d %d %d",w,x,y,z)
#define prn(x) printf("%d\n",x)
#define prn2(x,y) printf("%d %d\n",x,y)
#define prn3(x,y,z) printf("%d %d %d\n",x,y,z)
#define prn4(w,x,y,z) printf("%d %d %d %d\n",w,x,y,z)
#define memc(x,y) memcpy(&x,&y,sizeof(x))
#define mems(x,y) memset(x,y,sizeof(x))
#define fli() freopen("in.txt","r",stdin)
#define flo() freopen("out.txt","w",stdout)
#define Rep(i,x,v) for(int i=x;i<v;i++)
#define Repe(i,x,v) for(int i=x;i<=v;i++)
#define rep(i,v) for(int i=0;i<v;i++)
#define repe(i,v) for(int i=0;i<=v;i++)
#define Repr(i,x,v) for(int i=x;v<i;i--)
#define Repre(i,x,v) for(int i=x;v<=i;i--)
#define repr(i,x) for(int i=x;0<i;i--)
#define repre(i,x) for(int i=x;0<=i;i--)
#define repv(i,x) for(auto i=x.begin();i!=x.end();i++)
#define reprv(i,x) for(auto i=x.rbegin();i!=x.rend();i++)
#define Repn(i,x,v) for(int i=x;i<v;i++,putchar('\n'))
#define repn(i,v) for(int i=0;i<v;i++,putchar('\n'))
#define bl putchar('\n')
#define PI acos(-1)
#define ign cin.ignore(100,'\n')
#define gcc getchar()
#define pcc putchar
#define si size
#define fi first
#define se second
#define pf push_front
#define pof pop_front
#define pb push_back
#define pbb pop_back
#define mk make_pair
#define ll long long
#define ull unsigned long long
#define flerr 0.00000001
#define oo (ll)9e18
#define inf INT_MAX
#define maxintarrsize 536870911
#define MAX 505
using namespace std;
int nodes,edges,w,ed[MAX][MAX],aa,bb;
double ans;
struct edge { int to; int length; };
vector<edge>graph[MAX];
vector<int>x,y;
ll min_distance[MAX];
void dijkstra(int source) {
int where;
fill_n(min_distance,MAX,LLONG_MAX);
set< pair<long long,int> > active_vertices;
min_distance[ source ] = 0;
active_vertices.insert( {0,source} );
while (!active_vertices.empty()) {
where = active_vertices.begin()->second;
active_vertices.erase( active_vertices.begin() );
for (auto edge : graph[where]){
if (min_distance[edge.to] > min_distance[where] + edge.length) {
active_vertices.erase( { min_distance[edge.to], edge.to } );
min_distance[edge.to] = min_distance[where] + edge.length;
active_vertices.insert( { min_distance[edge.to], edge.to } );
}
}
}
}
int main(){
// fli();
int u,v,ss,c=1;
double tmp;
ll d1,d2,dd;
edge tt;
bool flag;
while(sc2(nodes,edges)==2,nodes or edges){
printf("System #%d\n",c++);
if(edges==0){
printf("The last domino falls after 0.0 seconds, at key domino 1.\n\n");
continue;
}
rep(i,edges){
sc3(u,v,w);
x.pb(u);
y.pb(v);
ed[u][v]=w;
ed[v][u]=w;
tt.to=v;tt.length=w;
graph[u].pb(tt);
tt.to=u;
graph[v].pb(tt);
}
dijkstra(1);
ans=0;
ss=x.si();
rep(i,ss){
u=x[i];
v=y[i];
d1=min_distance[x[i]];
d2=min_distance[y[i]];
if(d1==LLONG_MAX or d2==LLONG_MAX) continue;
if(d2>d1) swap(d1,d2),swap(u,v);
dd=d1-d2;
if(dd==ed[u][v]){
if(dd*1.0>ans or (dd*1.0==ans and flag==false) or (dd*1.0==ans and flag==true and u<aa)){
ans=dd;
aa=u;
flag=true;
}
}
else if(dd<ed[u][v]){
tmp=d1 + ( (ed[u][v]-(d1-d2))/2.0 );
if(tmp>ans){
ans=tmp;
aa=u;
bb=v;
if(aa>bb) swap(aa,bb);
flag=false;
}
else if(tmp==ans and flag==false){
if(u>v) swap(u,v);
if(u<aa){
ans=tmp;
aa=u;
bb=v;
flag=false;
}
}
}
}
if(flag){
printf("The last domino falls after %.1f seconds, at key domino %d.\n\n",ans,aa);
}
else{
printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n\n",ans,aa,bb);
}
Repe(i,1,nodes) graph[i].clear();
x.clear();
y.clear();
}
return 0;
}