#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int inf = 1000000009;

int n, m, M;
struct node {
	int v, state;
	node(){}
	node(int v, int state): v(v), state(state){}
};
struct data {
	int a, b, c, p, r;
	void in() {
		scanf("%d%d%d%d%d", &a, &b, &c, &p, &r);
		a--; b--; c--;
	}
}p[13];
int d[10][1034];
int vis[12];
int spfa() {
	int M = (1<<m);
	int i, j;
	queue <node> q;
	for(i = 0; i < n; i++)
		for(j = 0; j < M; j++)
			d[i][j] = inf;
	d[0][1] = 0;
	vis[0] = 1;
	q.push(node(0, 1));
	while(!q.empty()) {
		node u = q.front(); q.pop(); vis[u.v] = 0;
		for(i = 0; i < m; i++) if(p[i].a == u.v) {
			int inc;
			if(u.state&(1<<p[i].c)) inc = p[i].p;
			else inc = p[i].r;
			int now = d[u.v][u.state] + inc;
			int v = p[i].b;
			int tp = u.state|(1<<v);
			if(now < d[v][tp]) {
				d[v][tp] = now;
				if(!vis[v]) {
					vis[v] = 1;
                    q.push(node(v, tp));
				}
			}
		}
	}
	int ans = inf;
	for(i = 0; i < M; i++) ans = min(ans, d[n-1][i]);
	if(ans == inf) puts("impossible");
	else printf("%d\n", ans);
}
int main() {
	int i;
	while(~scanf("%d%d", &n, &m)) {
		for(i = 0; i < m; i++)
			p[i].in();
		spfa();
	}
	return 0;
}

• 难道你vis没开两维状态都可以A么...... (23) 2139607877 2017-09-12 20:11:20