is absolutly right. It's the main thing. Euler path.Ryan Pai
may be ur problem in dijkstra or BMF. check this.rafi7
Moderator: Board moderators
is absolutly right. It's the main thing. Euler path.Ryan Pai
may be ur problem in dijkstra or BMF. check this.rafi7
Code: Select all
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define FOR(a,b) for(int a=0;a<b;a++)
#define MAXI (50)
int mat[MAXI][MAXI];
int t[MAXI];
void clear() {
FOR(i,MAXI) FOR(j,MAXI) mat[i][j]=2<<10;
FOR(i,MAXI) t[i]=0;
}
void floyd() {
FOR(i,MAXI) FOR(j,MAXI) if(i!=j) FOR(k,MAXI) if(i!=k && j!=k)
mat[j][k] = min(mat[j][i]+mat[i][k],mat[j][k]);
}
int main() {
char lin[10001];
while(true) {
clear();
int tot = 0;
while(true) {
// reads a line, if it should stop, stop
if(!(gets(lin))) return 0;
if(strlen(lin)==0) continue;
// if deadend --> next
if(strcmp(lin,"deadend")==0) break;
// connects them
int d = lin[0]-'a';
int p = lin[strlen(lin)-1]-'a';
t[d]++; t[p]++;
tot += strlen(lin);
mat[d][p] = min(mat[d][lin[p]],(int) strlen(lin));
}
floyd();
FOR(i,MAXI) if(t[i]%2) {
for(int j=i+1;j<MAXI;j++) if(t[j]%2) {
cout << (mat[i][j]+tot) << endl;
goto n;
}
}
cout << tot << endl;
n:;
}
}
Code: Select all
Code removed!