记录编号	142786	评测结果	AAAAAAAAAA
题目名称	[国家集训队2011]星际探险	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.136 s
提交时间	2014-12-10 20:26:54	内存使用	0.75 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=5010,SIZEM=50010,INF=0x7fffffff/2;
int N,M,S,T;
int W[SIZEM]={0};
vector<pair<int,int> > c[SIZEN];
void SPFA(int f[],int S){
	static int inq[SIZEN]={0};
	static queue<int> Q;
	memset(inq,0,sizeof(inq));
	while(!Q.empty()) Q.pop();
	for(int i=0;i<N;i++) f[i]=INF;
	Q.push(S);f[S]=0;inq[S]=true;
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i].first,w=W[c[x][i].second];
			if(f[x]+w<f[u]){
				f[u]=f[x]+w;
				if(!inq[u]){
					inq[u]=true;
					Q.push(u);
				}
			}
		}
	}
}
int dist[SIZEN]={0};
int P;
int lis[SIZEN]={0};
int nxt[SIZEN]={0};
int ans[SIZEM]={0};
void work(void){
	
	for(int i=1;i<P;i++){
		int x=lis[i];
		for(int j=0;j<c[x].size();j++)
			if(c[x][j].first==lis[i+1]) nxt[i]=c[x][j].second;
	}
	int sum=0;
	for(int i=1;i<P;i++) sum+=W[nxt[i]];
	printf("%d\n",sum-dist[T]);
	for(int i=1;i<P;i++)
		ans[nxt[i]]=dist[lis[i+1]]-dist[lis[i]]-W[nxt[i]];
	for(int i=1;i<=M;i++) printf("%d\n",ans[i]);
}
void read(void){
	scanf("%d%d",&N,&M);
	int u,v;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&u,&v,&W[i]);
		c[u].push_back(make_pair(v,i));
	}
	scanf("%d",&P);
	for(int i=1;i<=P;i++) scanf("%d",&lis[i]);
	S=lis[1],T=lis[P];
}
int main(){
	freopen("exploration.in","r",stdin);
	freopen("exploration.out","w",stdout);
	read();
	SPFA(dist,S);
	work();
	return 0;
}