在这个地方dp[i][j]表示在i站剩下j units油的时候最小耗费。。。
大家给点建议。。。。谢谢。。。。。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 1000;
const int C = 101;
const int INFINITE = 0x7f7f7f7f;

class Edge
{
public:
	int t, w;
public:
	Edge ( int a, int b )
	{
		t = a;
		w = b;
	}
};

class Graph
{
public:
	vector <Edge> adj[N];
public:
	void addEdge ( int s, Edge e )
	{
		adj[s].push_back ( e );
	}
};

class Node
{
public:
	int v, left, cost;
public:
	Node ( int a, int b, int c )
	{
		v = a;
		left = b;
		cost = c;
	}
	
	bool operator < ( const Node node ) const
	{
		return cost > node.cost;
	}
};

Graph graph;
int dp[N][C], prices[N], n, m;
priority_queue <Node> q;

void dijtra( int c, int s, int t )
{
	memset (dp, 0x7f, sizeof ( dp ) );
	Node node ( 0, 0, 0 );

	q.push ( node );
	while ( !q.empty() ) 
	{
		Node tmp = q.top();
		q.pop();

		int v = tmp.v;
		int left = tmp.left;
		int cost = tmp.cost;

		if ( dp[v][left] == INFINITE )
		{
			dp[v][left] = cost;

			for ( int i = 0; i < graph.adj[v].size(); i++ )
			{
				Edge e = graph.adj[v].at( i );
				int next = e.t;
				int dis = e.w;
				int price = prices[v];            

				for ( int j = left; j <= c; j++ )
				{
					if ( j < dis )
						continue;
					int pay = ( j - left ) * price;
					q.push( Node ( next, j - dis, cost + pay ) );
				}
			}
		}
	}


	int result = INFINITE;
	for ( int k = 0; k <= c; k++ )
		result = result < dp[t][k] ? result : dp[t][k];
	if ( result < INFINITE )
		printf ( "%d\n", result );
	else
		printf ( "impossible\n" );
}

int main()
{
	int i, s, t, w, q, c;
	scanf ( "%d%d", &n, &m );
	for ( i = 0; i < n; i++ )
		scanf ( "%d", prices + i );
	for ( i = 0; i < m; i++ )
	{
		scanf ( "%d%d%d", &s, &t, &w );
		Edge e ( t, w );
		Edge f ( s, w );
		graph.addEdge ( s, e );
		graph.addEdge ( t, f );
	}

	scanf ( "%d", &q );
	for ( i = 0; i < q; i++ )
	{
		scanf ( "%d%d%d", &c, &s, &t ); 
		dijtra ( c, s, t );
	}

	return 0;
}

• 你的算法错了哦 扩展的时候队列只进不出 (0) Bzin 2009-04-13 12:33:13
  • Re:你的算法错了哦 扩展的时候队列只进不出 (0) zhenzhenhu 2010-11-18 22:43:20