中文题,不翻译不解释。
#include <iostream> #include <stdio.h> using namespace std; const int MAX=120; int M,N,X,T,V; int map[MAX][MAX]; int topo[MAX]; int visted[MAX]; typedef struct NODE { int level; int price; }NODE; NODE nodes[MAX]; int num=0; void Dfs(int v) { visted[v]=1; for (int i=1;i<=N;i++) { if (!visted[i] && map[v][i]>0)//unvisited { Dfs(i); } } topo[num++]=v; } void MinCost() { int i,j; for (i=0;i<N;i++) { for (j=i+1;j<N;j++) { if (map[topo[j]][topo[i]]>0) { int temp=nodes[topo[i]].price+map[topo[j]][topo[i]]; if ((temp<nodes[topo[j]].price)) { nodes[topo[j]].price=temp; } } } } printf("%d\n",nodes[1].price); } int main() { int i,j; memset(map,0,sizeof(map)); memset(visted,0,sizeof(visted)); scanf("%d%d",&M,&N); for (i=1;i<=N;i++) { scanf("%d%d%d",&nodes[i].price,&nodes[i].level,&X); for (j=1;j<=X;j++) { scanf("%d%d",&T,&V); map[i][T]=V; } if( abs(nodes[i].level-nodes[1].level) > M ) { for(j=1;j<N;j++) { map[j][i]=-1; } } } Dfs(1); MinCost(); return 0; }