为毛我交了后第一个点就wa了。。。。
by ywh666 @ 2018-10-17 12:06:42
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
long long n,head[1005],cnt,dis[1005],vis[1005],m,l,s,t,a[100005],b[100005],c[100005],mark[100005];
struct edge{long long to,v,next;
}e[200005];
void add(long long a,long long b,long long c)
{
e[cnt].to=b;
e[cnt].v=c;
e[cnt].next=head[a];
head[a]=cnt++;
}
void spfa()
{
queue<long long>q;
q.push(s);
memset(dis,0x3f3f3f,sizeof(dis));
dis[s]=0;
while(!q.empty())
{
long long u=q.front();
q.pop();
vis[u]=0;
for(long long i=head[u];i!=-1;i=e[i].next)
{
if(e[i].v==0)continue;
if(dis[u]+e[i].v<dis[e[i].to])
{
dis[e[i].to]=dis[u]+e[i].v;
if(!vis[e[i].to])
{
vis[e[i].to]=1;
q.push(e[i].to);
}
}
}
}
}
inline void read(long long &x)
{
x=0;
char c;
c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=getchar();
}
inline void write(long long x){
long long y=10,len=1;
while(y<=x) {y*=10;len++;}
while(len--){y/=10;putchar(x/y+48);x%=y;}
putchar(' ');
}
int main()
{
bool ok=0;
read(n);read(m);read(l);read(s);read(t);
memset(head,-1,sizeof(head));
cnt=0;
for(long long i=0;i<m;++i)
{
read(a[i]);read(b[i]);read(c[i]);
if(c[i]==0)
{
mark[i]=1;
c[i]=1;
}
add(a[i],b[i],c[i]);add(b[i],a[i],c[i]);
}
spfa();
if(dis[t]>l){puts("NO");return 0;
}
if(dis[t]==l)
{
ok=1;
}
long long gg=l-dis[t];
for(long long i=0;i<m;++i)
{
if(ok)break;
if(!mark[i])continue;
e[i*2].v+=gg;
e[i*2+1].v+=gg;
c[i]+=gg;
spfa();
if(dis[t]==l)
{
ok=1;
break;
}
else
gg=l-dis[t];
}
if(ok)
{
puts("YES");
for(long long i=0;i<m;++i)
{
write(a[i]);write(b[i]);write(c[i]);puts("");
}
return 0;
}
else {
puts("NO");
}
return 0;
}
by ywh666 @ 2018-10-17 12:07:24
@[albus_dembledore](/space/show?uid=55703)
## 不能给我发代码片吗?
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=1e3+5;
const int maxm=2e4+5;
const ll inf=1e18+5;
struct edge{
int u,v,next;
ll w;
}e[maxm];
int n,m,cnt,from,to;
int head[maxn],l;
ll dis[maxn][2];
bool vis[maxn];
void start(){
cnt=0;
memset(dis,0x3f,sizeof(dis));
memset(head,-1,sizeof(head));
memset(vis,false,sizeof(vis));
}
void adde(int u,int v,ll w){
e[cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;
}
void dijkstra(int pos){ //from 1
typedef pair<ll,int> pii; //to 0
priority_queue<pii,vector<pii>,greater<pii> >q;
int num=pos==from;
dis[pos][num]=0; q.push(make_pair(dis[pos][num],pos));
while(!q.empty()){
int u=q.top().second; q.pop();
if(vis[u]) continue; vis[u]=true;
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;
ll w=e[i].w;
if(num){
if(!w) w=max(l-dis[v][0]-dis[u][1],1ll);
e[i].w=e[i^1].w=w;
if(dis[v][num]>dis[u][num]+w){
dis[v][num]=dis[u][num]+w;
q.push(make_pair(dis[v][num],v));
}
}
else if(w && dis[v][num]>dis[u][num]+w){
dis[v][num]=dis[u][num]+w;
q.push(make_pair(dis[v][num],v));
}
}
}
}
int main(){
scanf("%d %d %lld %d %d",&n,&m,&l,&from,&to);
start();
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
adde(u,v,w);
adde(v,u,w);
}
dijkstra(to); if(dis[from][0]<l) {puts("NO");return 0;};
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++) dis[i][1]=dis[i][0];
dijkstra(from); if(dis[to][1]>l) {puts("NO");return 0;};
puts("YES");
for(int i=0;i<cnt;i+=2){
printf("%d %d %lld\n",e[i].u,e[i].v,e[i].w);
}
return 0;
}
```
by wangml @ 2018-10-17 12:13:10
# _**去掉了读入优化**_
by wangml @ 2018-10-17 12:14:08
这是标程
```
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define N 1004
#define M 10004
using namespace std;
typedef long long LL;
LL aans;
int cas,cass;
int n,m,lll,ans;
int S,T;
LL L;
int last[N];
LL d[N],dd[N];
bool u[N];
struct xxx
{
int from,to,next;
LL q;
}a[M<<1];
bool cmp(int a,int b)
{
return d[a]>d[b];
}
void add(int x,int y,int z)
{
a[++lll].next=last[x];
a[lll].from=x,a[lll].to=y;
a[lll].q=z;
last[x]=lll;
}
void dijkstra(bool f)
{
int i,j,k,now,to;
LL q;
mem(u,0);mem(d,14);
if(f)d[S]=0;
else d[T]=0;
for(i=0;i<n;i++)
{
for(j=0,now=n;j<n;j++)if(!u[j] && d[now]>d[j])now=j;
u[now]=1;
for(j=last[now];j;j=a[j].next)
{
to=a[j].to;
if(f)
{
q=a[j].q;
if(!q)q=max(L-d[now]-dd[to],1ll);
a[j].q=a[j^1].q=q;
d[to]=min(d[to],d[now]+a[j].q);
}
else if(a[j].q)
d[to]=min(d[to],d[now]+a[j].q);
}
}
}
int main()
{
int i,j,k;
int x,y,z;
while(~scanf("%d",&n))
{
scanf("%d%I64d%d%d",&m,&L,&S,&T);
lll=1;mem(last,0);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
dijkstra(0);
if(d[S]<L){puts("NO");continue;}
memcpy(dd,d,sizeof(dd));
dijkstra(1);
if(d[T]>L){puts("NO");continue;}
puts("YES");
for(i=2;i<=m+m;i+=2)
printf("%d %d %I64d\n",a[i].from,a[i].to,a[i].q);
}
return 0;
}
```
by wangml @ 2018-10-17 12:17:34
@[albus_dembledore](/space/show?uid=55703)
@[wangml](/space/show?uid=21656)
%%%%%%%%%%
by Iamacat @ 2018-10-17 20:24:18
@[Iamacat](/space/show?uid=44924) %%%%%%
by wangml @ 2018-10-18 19:04:42
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
int n,m,z,cnt,head[100005],p[100005],lca[100005][23][12],x[100005][23],dep[100005],ans[15],tot;
vector<int>v[100005];
struct edge{int to,next;
}e[200005];
void add(int a,int b)
{
e[cnt].to=b;
e[cnt].next=head[a];
head[a]=cnt++;
}
int min(int a,int b)
{
return a<b?a:b;
}
int log2(int x)
{
int tot=0;
x>>=1;
while(x)
{x>>=1;
tot++;
}return tot;
}
void dfs(int u,int pre,int d)
{
dep[u]=d;
x[u][0]=pre;
for(int i=1;i<=log2(d);++i)x[u][i]=x[x[u][i-1]][i-1];
for(int i=0;i<(min(v[u].size(),10));++i)
{
lca[u][0][i+1]=v[u][i];
}
for(int i=1;i<=log2(d);++i)
{
int a;
priority_queue<int,vector<int>,greater<int> >q;
for(int j=1;j<=10;++j)
{
if(lca[u][i-1][j]!=-1)q.push(lca[u][i-1][j]);
if(lca[x[u][i-1]][i-1][j]!=-1)q.push(lca[x[u][i-1]][i-1][j]);
}
a=1;
while(!q.empty()&&a<=10)
{
int g=q.top();
q.pop();
lca[u][i][a]=g;
a++;
}
}
for(int i=head[u];i!=-1;i=e[i].next)
{
if(e[i].to==pre)continue;
dfs(e[i].to,u,d+1);
}
}
void LCA(int a,int b,int c)
{
priority_queue<int,vector<int>,greater<int> >q;
if(dep[a]<dep[b])swap(a,b);
for(int i=log2(dep[a]);i>=0;--i)
{
if(dep[x[a][i]]>=dep[b])
{
for(int j=1;j<=10;++j)
{
if(lca[a][i][j]>=0)q.push(lca[a][i][j]);
}
a=x[a][i];
}
}
if(a==b)
{
for(int i=0;i<min(v[a].size(),10);++i)q.push(v[a][i]);
for(int j=1;j<=c;++j)
{
if(!q.empty())
{
tot++;
int u=q.top();
q.pop();
ans[tot]=u;
}
}
return ;
}
for(int i=log2(dep[a]);i>=0;--i)
{
if(x[a][i]!=x[b][i])
{
for(int j=1;j<=10;++j)
{
if(lca[a][i][j]>0)q.push(lca[a][i][j]);
}
a=x[a][i];
for(int j=1;j<=10;++j)
{
if(lca[b][i][j]>0)q.push(lca[b][i][j]);
}
b=x[b][i];
}
}
for(int i=1;i<=10;++i)
{
if(lca[a][0][i]!=-1)q.push(lca[a][0][i]);
if(lca[b][1][i]!=-1)q.push(lca[b][1][i]);
}
for(int j=1;j<=c;++j)
{
if(!q.empty())
{
tot++;
int u=q.top();
q.pop();
ans[j]=u;
}
}
return ;
}
int main()
{
memset(lca,-1,sizeof(lca));
memset(head,-1,sizeof(head));
cnt=0,tot=0;
int a,b,c;
scanf("%d%d%d",&n,&m,&z);
for(int i=1;i<n;++i)
{
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1;i<=m;++i)
{
scanf("%d",&p[i]);
v[p[i]].push_back(i);
}
dfs(1,-1,1);
for(int i=1;i<=z;++i)
{
tot=0;
scanf("%d%d%d",&a,&b,&c);
memset(ans,-1,sizeof(ans));
LCA(a,b,c);
printf("%d ",tot);
for(int j=1;j<=tot;++j)
{
printf("%d ",ans[j]);
}
puts("");
}
}
```
by ywh666 @ 2018-10-18 19:45:40