携程2018春招-大数据分析师在线笔试题-最长路径问题
最长路径问题
题目描述
现有A、B、C、D、E五个字符，以及M个字符串，每个字符串由这五个字符和1-9的整数间隔组成，
如：A2B3D，表示存在A->B 和 B->D的路径，且路径长度为2和3，可以推出A->D的一条路径长为5；
求最长的一条路径的长度，如果任何一处路径出现环（即出现A->···->A,B->···->B,C->···->C,D->···->D,E->···->E的路径，返回-1）
输入：
第一行为字符串的个数M第二行开始为M个字符串
输出：
最长的一条路径的长度，如果出现环，返回-1
样例输入：
4A2B3D
A4C2E
A5D
C3B
样例输出：
10
*********************************************************************************************************************
本人菜鸟，感觉应该是有向带权图的最长路径。
图这块我完全不会，所以做不来……
求大神来解答一番。
样例里就是A-4-C-3-B-3-D
*********************************************************************************************************************
static int calculate(int M, String[] strs) {
//write code here
}
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
int res;
int _M;
_M=Integer.parseInt(in.nextLine().trim());
int _str_size=_M;
String[] _strs=new String[_str_size];
String _strs_item;
for (int _strs_i=0;_strs_i<_str_size;_strs_i++) {
try {
_strs_item=in.nextLine();
} catch (Exception e) {
_strs_item=null;
}
_strs[_strs_i]=_strs_item;
}
res=calculate(_M,_strs);
System.out.println(String.valueOf(res));
}
My final answer. Floyd can solve it, but we need to check whether AB == 0;
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int maxSize = 5;
typedef struct { char vertex[maxSize]; int edge[maxSize][maxSize]; int n, e;
}MGraph;
int getVertex(char c) { char A, B, C, D, E; if(c == 'A') { return 0; } else if(c == 'B') { return 1; } else if(c == 'C') { return 2; } else if(c == 'D') { return 3; } else if(c == 'E') { return 4; }
}
int A[maxSize][maxSize];
int Path[maxSize][maxSize];
int Max = 0;
void maxfloyd(MGraph G) { int i, j ,k; for(i = 0; i < G.n; ++i) { for(j = 0; j < G.n; ++j) { A[i][j] = G.edge[i][j]; Path[i][j] = -1; } } for(k = 0; k < G.n; ++k) { for(i = 0; i < G.n; ++i) { for(j = 0; j < G.n; ++j) { if(A[i][k] > 0 && A[k][j] > 0 && A[i][k]+A[k][j] > A[i][j]) { A[i][j] = A[i][k]+A[k][j]; if(A[i][j] > Max) { Max = A[i][j]; } } } } }
}
int main() { int m, len, i, j; char str[10][10]; MGraph G; G.n= 5; while(scanf("%d", &m) != EOF) { for(i = 0; i < m; ++i) { scanf("%s", str[i]); len = strlen(str[i]); for(j = 0; j < len-2; j=j+2) { int a = getVertex(str[i][j]); int b = getVertex(str[i][j+2]); int c = str[i][j+1] - '0'; G.edge[a][b] = c; }
} maxfloyd(G); printf("%d", Max); }
}
查看11道真题和解析
