Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## spfa水题 ~~~秒A

Posted by 9974 at 2013-04-11 22:23:59 on Problem 3411
```#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;
}
```

Followed by: