Poj 3411 Paid Roads（最短路）

题目地址：http://poj.org/PRoblem?id=3411

思路：记录状态，松弛操作时判断即可。

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug
using namespace std;
const int maxn=15;
const int INF=0x3f3f3f3f;
struct Edge
{
    int v,c,p,r;
    Edge(int v=0,int c=0,int p=0,int r=0):v(v),c(c),p(p),r(r) {}
};
struct Node
{
    int u,s;
    Node(int u=0,int s=0):u(u),s(s) {}
};
int n,m;
queue<Node> q;
vector<Edge> g[maxn];
int v[maxn][1<<maxn];
int dist[maxn][1<<maxn];
void solve(int u,int s)
{
    memset(v,0,sizeof(v));
    while(!q.empty()) q.pop();
    for(int i=1; i<=n; i++)
        for(int j=0; j<(1<<n); j++)
            dist[i][j]=INF;
    v[u][s]=1,q.push(Node(u,s)),dist[u][s]=0;
    while(!q.empty())
    {
        Node now=q.front();
        q.pop(),v[now.u][now.s]=0;
        for(int i=0; i<g[now.u].size(); i++)
        {
            Edge nt=g[now.u][i];
            int tmp=now.s|(1<<(nt.v-1));
            if(now.s&(1<<(nt.c-1)))
            {
                if(dist[nt.v][tmp]>dist[now.u][now.s]+nt.p)
                {
                    dist[nt.v][tmp]=dist[now.u][now.s]+nt.p;
                    if(!v[nt.v][tmp])
                    {
                        v[nt.v][tmp]=1;
                        q.push(Node(nt.v,tmp));
                    }
                }
            }
            else
            {
                if(dist[nt.v][tmp]>dist[now.u][now.s]+nt.r)
                {
                    dist[nt.v][tmp]=dist[now.u][now.s]+nt.r;
                    if(!v[nt.v][tmp])
                    {
                        v[nt.v][tmp]=1;
                        q.push(Node(nt.v,tmp));
                    }
                }
            }
        }
    }
    int ans=INF;
    for(int i=(1<<(n-1)); i<(1<<n); i++)
        ans=min(ans,dist[n][i]);
    if(ans>=INF) printf("impossible\n");
    else printf("%d\n",ans);
}
int main()
{
#ifdef debug
    freopen("in.in","r",stdin);
#endif // debug
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; i++)
    {
        int a,b,c,p,r;
        scanf("%d%d%d%d%d",&a,&b,&c,&p,&r);
        g[a].push_back(Edge(b,c,p,r));
    }
    solve(1,1);
    return 0;
}