Poj 3411 Paid Roads（最短路）

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

#include<cstdio>#include<queue>#include<cstring>#include<iostream>#include<algorithm>#define debugusing 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;}