Gym 101617JTreasure Map（bfs暴力）

http://codeforces.com/gym/101617/attachments

题意：
给出一个图，每个顶点代表一个金矿，每个金矿有g和d两个值，g代表金矿初始的金子量，d是该金矿每天的金子量会减少d。顶点与顶点之间存在边，意思是从一个金矿到另一个金矿需要花费的天数。现在有个人一开始在1金矿，问最多能挖到多少金矿，注意，不能在一个金矿连续挖几天。

思路：
bfs求解，但是需要剪枝，用二位数组d[v][day]记录第day天时在v金矿所能获得的最大值。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int maxn = +;

 int tot,n,m,mx,ans;

 int head[maxn];

 int g[maxn],d[maxn];

 int dis[maxn][maxn];

 struct Node

 {

     int v,w,next;

 }e[*maxn];

 struct node

 {

     int id;

     int val;

     int day;

     bool operator< (const node& rhs) const

     {

         return day>rhs.day;

     }

 };

 void addEdge(int u,int v,int w)

 {

     e[tot].v = v;

     e[tot].w = w;

     e[tot].next = head[u];

     head[u] = tot++;

 }

 void bfs()

 {

     memset(dis,,sizeof(dis));

     priority_queue<node> q;

     node p;

     p.id = ;

     p.val = g[];

     p.day = ;

     q.push(p);

     ans = g[];

     dis[][] = g[];

     while(!q.empty())

     {

         p = q.top(); q.pop();

         int u = p.id;

         for(int i=head[u];i!=-;i=e[i].next)

         {

             int v = e[i].v;

             int w = e[i].w;

             node tmp = p;

             tmp.id = v;

             tmp.val += max(,g[v]-d[v]*(p.day+w-));

             tmp.day = p.day + w;

             if(tmp.day>mx)  continue;

             if(tmp.val<=dis[v][tmp.day])  continue;

             dis[v][tmp.day] = tmp.val;

             q.push(tmp);

             ans = max(ans,tmp.val);

         }

     }

 }

 int main()

 {

    //freopen("in.txt","r",stdin);

     while(~scanf("%d%d",&n,&m))

     {

         mx = ;

         tot = ;

         memset(head,-,sizeof(head));

         for(int i=;i<=n;i++)

         {

             scanf("%d%d",&g[i],&d[i]);

             mx = max(mx,g[i]/d[i]+);

         }

         while(m--)

         {

             int u,v,w;

             scanf("%d%d%d",&u,&v,&w);

             addEdge(u,v,w);

             addEdge(v,u,w);

         }

         bfs();

         printf("%d\n",ans);

     }

     return ;

 }