[ codeforces ] 2015 German Collegiate Programming Contest (GCPC 15) + POI 10-T3 Problem M. Sums

題目:
http://codeforces.com/gym/100753

解法:
這是POI的題目，困難度很高，主要想法是使用最短路徑
設a[i]=集合中第i個元素
則d[x]=最小的K滿足 (K-x)整除於a[0]，0<=x<a[0]
可以用dijkstra得到d陣列
用SPFA則會有TLE的風險
最後詢問Q是否d[Q%a[0]]<=Q，如果滿足條件表示Q可以由集合內的數字組成

code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include <bits/stdc++.h> using namespace std; int INF=2000000000,s[5005],d[50005]; set<pair<int,int > > st; int t,n,a; int main(){ scanf("%d",&n); for(int i=0;i<n;++i)scanf("%d",&s[i]); for(int i=0;i<s[0];++i)d[i]=INF; d[0]=0; st.insert(make_pair(d[0],0)); while(!st.empty()){ pair<int,int> top=*st.begin(); st.erase(top); int v=top.second; int x=top.first; for(int i=1;i<n;++i){ int x2=x+s[i]; int v2=(v+s[i])%s[0]; if(x2<d[v2]){ if(d[v2]<INF)st.erase(make_pair(d[v2],v2)); d[v2]=x2; st.insert(make_pair(d[v2],v2)); } } } scanf("%d",&m); while(m--){ scanf("%d",&a); if(d[a%s[0]]<=a)printf("TAK\n"); else printf("NIE\n"); } return 0; }