练习！！
这里主要需要注意的是进队的条件和dp[][]状态的控制，dp[i][j]表示到第i个城市剩余汽油为j的最小花费。
代码：
#include#include #include #include #define inf 100000000#define MAXN 1200#define MAXM 1200using namespace std;int head[MAXN],price[MAXN],dp[MAXN][120],vis[MAXN][120];int temp,n,m;struct Node{ int v,len,next;}edge[2*MAXN*10];struct Node1{ int d; int u; int cost; Node1(int x,int y,int z) { u=x; d=y; cost=z; } friend bool operator < (Node1 a,Node1 b) { return a.cost>b.cost; }};void addEdge(int x ,int y ,int c){ edge[temp].v=x; edge[temp].len=c; edge[temp].next=head[y]; head[y]=temp; temp++; edge[temp].v=y; edge[temp].len=c; edge[temp].next=head[x]; head[x]=temp; temp++;}priority_queue que;int Dijstra(int s,int t,int c){ while(!que.empty())que.pop(); for(int i=0;i<=n;i++) { for(int j=0;j<=c;j++) { dp[i][j]=inf; } } memset(vis,0,sizeof(vis)); dp[s][0]=0; que.push(Node1(s,0,0)); while(!que.empty()) { Node1 b=que.top(); que.pop(); int u=b.u; int d=b.d; int cost=b.cost; vis[u][d]=1; if(u==t) return cost; if(d+1<=c&&!vis[u][d+1]&&dp[u][d+1]>dp[u][d]+price[u]) { dp[u][d+1]=dp[u][d]+price[u]; que.push(Node1(u,d+1,dp[u][d+1])); } for(int i=head[u];i!=-1;i=edge[i].next) { int v; v=edge[i].v; int len=edge[i].len; if(d>=len&&!vis[v][d-len]&&dp[v][d-len]>cost) { dp[v][d-len]=cost; que.push(Node1(v,d-len,cost)); } } } return -1;}int main(){while(scanf("%d%d",&n,&m)!=EOF){ for(int i=0;i