记录编号	427525	评测结果	AAAAAAAAAA
题目名称	[国家集训队2011]星际探险	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.121 s
提交时间	2017-07-22 11:08:03	内存使用	130.66 MiB

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef long long LL;
void read(int &x) {static char c; static bool flag;for (flag = 0; (c=getchar())<'0'||c>'9'; flag |= c=='-');for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=x*10+c-'0');if(flag) x = -x;}

#define N 510000
struct E {int to,next,w;}g[N*20];
int fr[N],tot,ans;
 
void Add(int from,int to,int w) {
	g[++tot].to = to;
	g[tot].w = w;
	g[tot].next = fr[from];
	fr[from] = tot;
}
 
int n,m,a[N],add[N],pr[N],q; 
int d[N],inq[N],c[N]; 
 
void spfa(int s) {
    static queue<int> q;
    memset(d,127/3,sizeof(d[0])*(n+3));
    q.push(s); d[s] = 0; 
    while (q.size()) {
        int t = q.front(); q.pop(); inq[t] = 0;
        for (int i = fr[t]; i; i = g[i].next) {
            int to = g[i].to;
            //if (t == pr[to]) dd[to] = dd[t]+g[i].w;
            if (d[to] > d[t]+g[i].w) {
                d[to] = d[t]+g[i].w;
                if(inq[to] != s) {
                    q.push(to);
                    inq[to] = s;
                }
            }
        }
    }
    q.push(s); 
    while (q.size()) {
        int t = q.front(); q.pop(); 
        for (int i = fr[t]; i; i = g[i].next) {
            int to = g[i].to;
            if (t == pr[to]) { 
			   c[i] = d[to]-(d[t]+g[i].w);
               q.push(to);
			}
        }
    }
}
 
int main() {
    freopen("exploration.in","r",stdin);freopen("exploration.out","w",stdout);
    read(n); read(m);
    for (int i = 1,u,v,w; i <= m; i++) {
    	read(u); read(v); read(w);
    	Add(u+1,v+1,w);
	}
	read(q);	
	for (int i = 1; i <= q; i++) {
	   read(a[i]); a[i]++; 
	   pr[a[i]] = a[i-1];
	}
	spfa(a[1]);	ans = 0;
	for (int i = 1; i <= m; i++) ans += c[i]>0?c[i]:-c[i]; 
	printf("%d\n",ans);
	for (int i = 1; i <= m; i++) printf("%d\n",c[i]);
    return 0;
}