题意

一个道路网连接了N个城市(从1个城市到N个城市)，可能有一条以上的道路连接一个城市和另一个城市。有些道路是有偿的。从城市Ai到城市Bi，有两种方式支付旅行费用: 在城市Ci提前支付pi(Ci可能不等于Ai); 出差后在城市Bi支付。它花费了Ri。

编写一个程序，从城市1到城市N找到一个最低成本的路线。

Input

输入的第一行包含N和m的值，下面的m行通过指定ai、bi、ci、Pi、Ri的值来描述一条路。同一行的相邻值由一个或多个空格分隔。所有值是整数,1≤m,N≤10 0≤R P≤≤100。

Output

文件中唯一的一行必须包含从城市1到城市的最小可能的花费。如果因为任何原因，旅行是不可能的，你应该把“不可能”这个词写出来。

Sample Input

4 5
1 2 1 10 10
2 3 1 30 50
3 4 3 80 80
2 1 2 10 10
1 3 2 10 50

Sample Output

110

题解

状态压缩+dijkstra

1. dp[i][s]:=走到i点时的最优解，且此时走过的点状态为s
2. 按照普通的DAG状态压缩的做法是错误的，因为这种做法只能使用于有向无环图。而题目中的图可能存在环，所以只能按照dijkstra来进行松弛操作的同时进行状态转移。
3. 题目中的某个点可能经过多次

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const LL LNF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

const int N=15;
struct Edge
{
    int to;
    int c,p;
    int r;
};
struct Node
{
    int to;
    int s;
    int dis;
    bool operator>(const Node &W) const
    {
        return dis>W.dis;
    }
};
vector<Edge> g[N];
int dist[N][1<<10];
bool vis[N][1<<10];
int n,m;

void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    priority_queue<Node,vector<Node>,greater<Node> > heap;
    dist[0][1]=0;
    heap.push({0,1,0});

    while(heap.size())
    {
        Node t=heap.top();
        heap.pop();
        int u=t.to,s=t.s;

        if(vis[u][s]) continue;
        vis[u][s]=true;

        for(int i=0;i<g[u].size();i++)
        {
            Edge j=g[u][i];
            int v=j.to;

            for(int s=0;s<1<<n;s++)
                if(s>>u & 1)//枚举的状态必须包含u，但可能同时包含v。因为可能重复路径
                {
                    int ns=s | 1<<v;
                    if(dist[v][ns] > dist[u][s]+j.r)
                    {
                        dist[v][ns] = dist[u][s]+j.r;
                        heap.push({v,ns,dist[v][ns]});
                    }
                    if((s>>j.c & 1) && dist[v][ns] > dist[u][s]+j.p)
                    {
                        dist[v][ns] = dist[u][s]+j.p;
                        heap.push({v,ns,dist[v][ns]});
                    }
                }
        }
    }
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<m;i++)
    {
        int a,b,c,p,r;
        cin>>a>>b>>c>>p>>r;
        a--,b--,c--;
        g[a].push_back({b,c,p,r});
    }

    dijkstra();

    int res=INF;
    for(int s=0;s<1<<n;s++)
        res=min(res,dist[n-1][s]);

    if(res == INF) puts("impossible");
    else cout<<res<<endl;
    // system("pause");
}