WA UVa 10806 Dijkstra, Dijkstra.

无向图，求从1出发到n再回到1的最短路，不能重复走同一条边。

错误思路：先求出1到n的最短路，删去经过的边，再求一次最短路，相加,容易找到反例。

# include <cstdio>
# include <cstring>
# include <queue>
# include <algorithm>

using namespace std;

# define N 100 + 5
# define INF 0x3c3c3c3c

int n, m;
int pre[N], d[N];
int w[N][N];

void destory(void)
{
    for (int x = n; x != 1; x = pre[x])
    {
        w[x][pre[x]] = w[pre[x]][x] = INF;
    }
}

void read_graph(void)
{    
    int x, y, z;
    scanf("%d", &m);
    for (int i = 1; i <= n; ++i) 
        memset(w[i]+1, 0x3c, sizeof(int)*n);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &x, &y, &z);
        w[x][y] = w[y][x] = z;
    }
}

int dijkstra(int src, int des)
{
    typedef pair <int, int> pii;
    for (int i = 1; i <= n; ++i) d[i] = (i==src ? 0:INF);
    priority_queue < pii, vector<pii>, greater<pii> > Q;
    Q.push(make_pair(d[src], src));
    while (!Q.empty())
    {
        pii cur = Q.top(); Q.pop();
        int x = cur.second;
        if (x == des) return d[des];
        if (cur.first != d[x]) continue;
        for (int y = 1; y <= n; ++y) if (d[y] > d[x]+w[x][y])
        {
            d[y] = d[x] + w[x][y];
            pre[y] = x;
            Q.push(make_pair(d[y], y));
        }
    }
    return d[des];
}

int main()
{
    int ans;
        
    int icase = 0;
    while (scanf("%d", &n), n)
    {
        ++icase;
        if (icase != 1) putchar('\n');
        ans = 0;
        read_graph();
        ans += dijkstra(1, n);
        destory();
        ans += dijkstra(1, n);
        if (ans >= INF)
            printf("Back to jail");
        else
            printf("%d", ans);
    }

    return 0;
}

这是网络流的题目。