题目背景
小E有时喜欢吸PG
题目描述
小E的玩的受望先锋被疼讯代理了,于是他需要买英雄或合成英雄。。。
受望先锋有N个英雄是从1到n号的,每个都是明码标价的。
规则:获得一个英雄有两种方式:
-
直接购买该英雄,第i种英雄每个花费的金币为ci
- 用两个其他英雄合成所需的英雄(原先的两个在合成后被消耗),一共有m种合成方式。
请帮助小E用最少的金币获得编号为1的英雄1个。
输入输出格式
输入格式:
第一行有两个整数n,m,分别表示有n种英雄以及m种合成方式。
接下来一行有n个整数,第i个整数ci表示第i种英雄的单价。
接下来m行,每行3个整数ai,xi,yi,表示用英雄xi和yi可以合成英雄ai.
输出格式:
一行,一个整数表示获取英雄1的最少花费。
输入输出样例
输入样例#1:
5 3 5 0 1 2 5 5 2 3 4 2 3 1 4 5
输出样例#1:
2
说明
1≤n≤10000
0≤m≤100000
0≤ci≤10^9
1≤ai,xi,yi≤n (ai≠xi, xi≠yi, yi≠ai)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SPFA+神奇的思路~
感觉就是存边和别的不一样,存两次互相联系,刚开始要把所有点都放入队列,因为最后要推到一个点嘛。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define ll long longll n,m,fi[10001],ne[200001],w1[200001],w2[200001],cnt,f[10001],x,y,z;
bool b[10001];
queue<int> q;void add(ll u,ll v,ll k)
{w1[++cnt]=v;w2[cnt]=k;ne[cnt]=fi[u];fi[u]=cnt;
}ll read()
{ll f=1,tot=0;char c=getchar();while(c<'0' || c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') {tot=tot*10+c-'0';c=getchar();}return f*tot;
}void spfa()
{for(int i=1;i<=n;i++) b[i]=1,q.push(i);while(!q.empty()){int k=q.front();q.pop();b[k]=0;for(int i=fi[k];i;i=ne[i])if(f[w1[i]]>f[k]+f[w2[i]]){f[w1[i]]=f[k]+f[w2[i]];if(!b[w1[i]]){b[w1[i]]=1;q.push(w1[i]);}}}
}int main()
{freopen("dwarf.in","r",stdin);freopen("dwarf.out","w",stdout);n=read();m=read();for(ll i=1;i<=n;i++) f[i]=read();if(!f[1]){printf("0\n");return 0;}for(ll i=1;i<=m;i++){x=read();y=read();z=read();add(y,x,z);add(z,x,y);}spfa();printf("%lld\n",f[1]);return 0;
}
下面这个是树形DP做的,60分,不知道是哪里WA了,总感觉思路是对的……
#include<cstdio>
#include<cstring>
#define ll long longll n,m,fi[10001],ne[100001],w1[100001],w2[100001],cnt,f[10001],x,y,z;
bool b[10001];ll read()
{ll f=1,tot=0;char c=getchar();while(c<'0' || c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') {tot=tot*10+c-'0';c=getchar();}return f*tot;
}void add(ll u,ll v,ll k)
{w1[++cnt]=v;w2[cnt]=k;ne[cnt]=fi[u];fi[u]=cnt;
}ll min(ll u,ll v)
{return u<v ? u:v;
}ll findd(ll u)
{if(b[u]) return f[u];b[u]=1;for(ll i=fi[u];i;i=ne[i]) f[u]=min(f[u],findd(w1[i])+findd(w2[i]));return f[u];
}int main()
{freopen("dwarf.in","r",stdin);freopen("dwarf.out","w",stdout);n=read();m=read();for(ll i=1;i<=n;i++) f[i]=read();if(!f[1]){printf("0\n");return 0;}for(ll i=1;i<=m;i++){x=read();y=read();z=read();add(x,y,z);}printf("%lld\n",findd(1));return 0;
}