SGU 185 Two shortest 5/10

就是隨便弄，但他有卡記憶體

所以你先弄個dijkstra，把邊刪一刪

順便就把題目變成了最大流

流一流，然後再做兩次遍歷就結束了

重點就是不要用vector，容易MLE！

隨便開個陣列就好了。

因為他的N小小的，所以O(N^2)沒差

//By momo
#include
#include
#include
#include

#define N 410
#define INF 9000000
#define PB push_back
#define SZ(x) (int)(x).size()
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)

using namespace std;

int n, m, vst[N], dis[N], tbl[N][N], che[N][N];
bool dfs(int p){
    vst[p] = 1; if(p == n) return 1;
    for(int i = 1; i <= n; i++)
        if(!vst[i] && tbl[p][i] && dfs(i))
            return tbl[p][i] = 0, tbl[i][p] = 1, 1;
    return 0;
}

bool print(int p){
    if(p == n) return printf("%d\n", p), 1;
    printf("%d ", p);
    for(int i = 1; i <= n; i++)
        if(!tbl[p][i] && che[p][i] && print(i))
            return che[p][i] = 0, 1;
    return 0;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            tbl[i][j] = INF;
    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        tbl[a][b] = tbl[b][a] = c;
    }
    fill(vst, vst+n+1, 0);
    fill(dis, dis+n+1, INF); dis[1] = 0;
    while(1){
        int mn = INF, x = 0;
        for(int i = 1; i <= n; i++)
            if(mn > dis[i] && !vst[i]) mn = dis[i], x = i;
        if(mn == INF) break; vst[x] = 1;
        for(int i = 1; i <= n; i++)
            dis[i] = min(dis[x]+tbl[i][x], dis[i]);
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++)
        tbl[i][j] = che[i][j] =
        (tbl[i][j] != INF && dis[i]+tbl[i][j] == dis[j]);
    for(int i = 0; i < 2; i++){
        fill(vst, vst+n+1, 0);
        if(dfs(1) == 0) return puts("No solution"), 0;
    }
    print(1); print(1);
}