题意：
给一个矩形，矩形中某些点有一定数量的矿石，有些点为传送点，有些点为障碍。你驾驶采矿车(ore-miner truck，我也不知道是什么)，从左上角出发，采尽量多的矿石，矿石不可再生。不能往左边或者上面走。传送点可以往左边或上面传。2<=n，m<=40
分析：
可以把矩形看作一张图，每个格子为一个点，每个格子与它右边和下面的点连接一条有向边。每个传送点与它传送的位置连接一条有向边。如果右边或下面为#那么不连。值得注意的是题目并没有保证传送点传送到的一定不是#，所以需要进行判断。
这样，我们得到了一个点数|V|=n*m，边数最大|E|=O(n*m)的有向有环图。答案就是限制只能取一次的最长路。
我们现在的任务就是把只能取一次抽象成另一种能实现的东西，不然暴力是指数级的。
很显然，向后传送不需要考虑，只考虑传回前面，在图上的表现为成环，或者说同属一个强连通分量。
很自然地就可以发现同属一个强连通分量的点都可以同时取到，我们考虑用tarjan缩点，这样建的就是一个DAG，在这个DAG上跑最长路，就是答案。
这里值得一提的是，这里不能用dijkstra，同时我们可以下结论：求最长路时，dijkstra算法只适用于负权图，求最短路时，dijkstra算法只适用于正权图。所以这里要写SPFA。
代码：用emacs写的，所以不要吐槽两格缩进
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
int low[],dfn[],arr[],scc[],al,cl,w[];
vector<int> g[];
vector<int> ng[];
stack <int> sta;
void tarjan(int now){
low[now]=dfn[now]=++cl;
sta.push(now);
for(int i=;i<g[now].size();i++){
int k=g[now][i];
if(arr[k])continue;
if(!dfn[k]){
tarjan(k);
low[now]=min(low[now],low[k]);
}else
low[now]=min(low[now],dfn[k]);
}
if(low[now]==dfn[now]){
al++;
while(){
int u=sta.top();
sta.pop();
arr[u]=;
scc[u]=al;
if(u==now) break;
}
}
}
int a[][];
void readint(int n,int m){
memset(arr,,sizeof(arr));
memset(w,,sizeof(w));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(scc,,sizeof(scc));
al=cl=;
for(int i=;i<=n*m;i++)g[i].clear(),ng[i].clear();
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
char x;cin>>x;
if(x=='*')a[i][j]=;
else
if(x=='#')a[i][j]=-;
else a[i][j]=(int)(x-);
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(j+<=m&&a[i][j+]!=-)g[i*m-m+j].push_back(i*m-m+j+);
if(i+<=n&&a[i+][j]!=-)g[i*m-m+j].push_back(i*m+j);
if(a[i][j]==){
int x,y;cin>>x>>y;
if(a[x+][y+]==-)continue;
else g[i*m-m+j].push_back(x*m+y+);
}
}
}
}
void dij(int n){//SPFA找最长路
queue <int> que;
int dist[];
memset(dist,,sizeof(dist));
dist[scc[]]=w[scc[]];
que.push(scc[]);
while(!que.empty()){
int k=que.front();
for(int i=;i<ng[k].size();i++){
if(dist[k]+w[ng[k][i]]>dist[ng[k][i]]){
dist[ng[k][i]]=dist[k]+w[ng[k][i]];
que.push(ng[k][i]);
}
}
que.pop();
}
int maxx=;
for(int i=;i<=n;i++)maxx=max(maxx,dist[i]);
cout<<maxx<<endl;
} int main(){
int t;cin >> t;
while(t--){
int n,m;
cin>>n>>m;
readint(n,m);
for(int i=;i<=n*m;i++)
if(!arr[i])
tarjan(i);//求强连通分量
for(int i=;i<=n*m;i++){
for(int j=;j<g[i].size();j++){
if(scc[i]==scc[g[i][j]])continue;
ng[scc[i]].push_back(scc[g[i][j]]);
}
}//缩点
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(a[i][j]==-||a[i][j]==)continue;
w[scc[i*m-m+j]]+=a[i][j];
}
}//算新的点权
dij(al);//求最长路
}
return ;
111 }