ALGORITHM NOTE ZigzagACM-ICPC 2008 Aizu, Problem J: Zigzag 解説の通り Dijkstra で解いてみました。 与えられた点を通る２つの直線の組み合わせについて、交点を求め, その交点と入力された点の集合について TSP を解くような感じです。 状態は S[現在の点(入力された点のみ)][前にいた点][通った点の状態(入力された点のみ)] になります。 ただし、無駄な交点を作ってしまうとTLEになります。 コードは, Dijkstra の部分のみです。 void dijkstra(){ priority_queue<QState> PQ[5]; bool C[10][MAX][SMAX]; rep(i, nnode) rep(j, n) rep(k, (1<<nnode)) C[i][j][k]= false; rep(s, nnode) rep(i, P[s].size)
