题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2851
题目大意：给出N条路径，M个终点（是路径的编号） 。重合的路径才算连通的，且路径是单向的。每条路径都有一个cost。求到达指定路径的最小cost。
解题思路：
题目读懂了，但是却看不懂样例。
题目中的最小单位路径应该看成一个点，cost在点上。
建图
枚举任意两条路径$i$、$j$，如果有交叉，即$E[i]>=S[j]$那么从i到j连一条有向边。cost保留在$W[i]$、$W[j]$上。
Dijkstra
由于起点必须在第一条路径，所以d[1]=W[1]，其余d[i]=inf。
Dijkstra后，再输入对于每个终点，d[des]就是结果。
代码
#include "cstdio"
#include "queue"
#include "cstring"
using namespace std;
#define maxn 2005
#define inf 0x3f3f3f3f
int head[maxn],tot,vis[maxn],S[maxn],E[maxn],W[maxn],d[maxn];
int T,n,m,des;
struct Edge
{
int to,next,w;
}e[maxn*maxn];
struct status
{
int d,p;
status(int d,int p):d(d),p(p) {}
bool operator < (const status &a) const {return d>a.d;}
};
void addedge(int u,int v)
{
e[tot].to=v;
e[tot].next=head[u];
head[u]=tot++;
}
void dijkstra(int s)
{
memset(vis,,sizeof(vis));
priority_queue<status> Q;
Q.push(status(,s));
for(int i=;i<=n;i++) d[i]=(i==s?W[s]:inf);
while(!Q.empty())
{
status x=Q.top();Q.pop();
int u=x.p;
if(vis[u]) continue;
for(int i=head[u];i!=-;i=e[i].next)
{
int v=e[i].to;
if(d[u]+W[v]<d[v])
{
d[v]=d[u]+W[v];
Q.push(status(d[v],v));
}
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
tot=;
memset(head,-,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d%d%d",&S[i],&E[i],&W[i]);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
if(E[i]>=S[j]) addedge(i,j);
dijkstra();
for(int i=;i<=m;i++)
{
scanf("%d",&des);
if(d[des]!=inf) printf("%d\n",d[des]);
else printf("-1\n");
}
}
}