学步园

/*

纯手写的Dijkstra, 优先级队列也是手工写的

*/

#include <iostream><br /> #include <cstring><br /> #define MAX_N 1000 //最大结点数<br /> using namespace std;<br /> //邻接表<br /> struct head<br /> {<br /> int from, to, weight;<br /> head * next;<br /> head()<br /> {<br /> from = to = 0;<br /> next = NULL;<br /> }<br /> }*heads[MAX_N + 1];<br /> int dist[MAX_N + 1]; //记录最短路径<br /> int n;<br /> int heap[MAX_N + 1]; //邻接表<br /> char temp[20];<br /> bool inQueue[MAX_N + 1]; //标识当前节点是否在队列中<br /> //插入边[from, to, weight]<br /> void insert(int from, int to, int weight)<br /> {<br /> head *newNode = new head();<br /> newNode->from = from;<br /> newNode->to = to;<br /> newNode->weight = weight;<br /> newNode->next = heads[from];<br /> heads[from] = newNode;<br /> }<br /> //结点p的左孩子<br /> int left(int p)<br /> {<br /> return p * 2;<br /> }<br /> //结点p的右孩子<br /> int right(int p)<br /> {<br /> return p * 2 + 1;<br /> }<br /> //结点p的父亲<br /> int parent(int p)<br /> {<br /> return p / 2;<br /> }<br /> //取堆的大小<br /> int heapSize()<br /> {<br /> return heap[0];<br /> }<br /> //增加堆的大小change<br /> void changeHeapSize(int change)<br /> {<br /> heap[0] += change;<br /> }<br /> //比较两个堆元素对应结点的距离大小<br /> int compare(int p1, int p2)<br /> {<br /> int dist1 = dist[heap[p1]];<br /> int dist2 = dist[heap[p2]];<br /> if(dist1 > dist2) return -1;<br /> else if(dist1 == dist2) return 0;<br /> else return 1;<br /> }<br /> //从结点n开始调整堆<br /> void maxHeapify(int p)<br /> {<br /> int l = left(p), r = right(p), largest;<br /> if(l <= heapSize() && compare(l, p) > 0)<br /> largest = l;<br /> else largest = p;<br /> if(r <= heapSize() && compare(r, largest) > 0)<br /> largest = r;<br /> if(largest != p)<br /> {<br /> int temp = heap[p];<br /> heap[p] = heap[largest];<br /> heap[largest] = temp;<br /> maxHeapify(largest);<br /> }<br /> }<br /> //弹出堆中最大值<br /> int popHeapMax()<br /> {<br /> if(heapSize() < 1) return -1;<br /> int maxVal = heap[1];<br /> inQueue[maxVal] = false;<br /> heap[1] = heap[heapSize()];<br /> changeHeapSize(-1);<br /> maxHeapify(1);<br /> return maxVal;<br /> }<br /> //得到val在堆中的下标<br /> int getHeapPos(int val)<br /> {<br /> /*int curPos = 1;<br /> while(heap[curPos] != 0 && heap[curPos] != val)<br /> {<br /> if(val < heap[curPos]) curPos = left(curPos);<br /> else curPos = right(curPos);<br /> }<br /> return curPos;*/<br /> for(int i = 1; i <= heapSize(); i++)<br /> if(heap[i] == val)<br /> return i;<br /> return -1;<br /> }<br /> //更新堆，从pos往上更新<br /> void updateHeapPos(int pos)<br /> {<br /> while(pos > 1 && compare(pos, parent(pos)) > 0)<br /> {<br /> int temp = heap[pos];<br /> heap[pos] = heap[parent(pos)];<br /> heap[parent(pos)] = temp;<br /> pos = parent(pos);<br /> }<br /> }<br /> 插入堆元素<br /> void heapInsert(int posVal)<br /> {<br /> changeHeapSize(1);<br /> heap[heapSize()] = posVal;<br /> updateHeapPos(heapSize());<br /> }<br /> void init()<br /> {<br /> heap[0] = 0;<br /> //heap[1] = 1;<br /> inQueue[0] = true;<br /> for(int i = 1; i <= n; i++)<br /> {<br /> inQueue[i] = true;<br /> heads[i] = NULL;<br /> dist[i] = INT_MAX;<br /> heapInsert(i);<br /> }<br /> dist[1] = 0;<br /> }<br /> void dijkstra()<br /> {<br /> while(heapSize() != 0)<br /> {<br /> int maxNode = popHeapMax();<br /> int curDist = dist[maxNode];<br /> head * curHead = heads[maxNode];<br /> while(curHead != NULL)<br /> {<br /> int nextNode = curHead->to;<br /> if(inQueue[nextNode])<br /> {<br /> if(curDist + curHead->weight < dist[nextNode])<br /> {<br /> dist[nextNode] = curDist + curHead->weight;<br /> updateHeapPos(getHeapPos(nextNode));<br /> }<br /> }<br /> curHead = curHead->next;<br /> }<br /> }<br /> }<br /> int getNum()<br /> {<br /> int i, len = strlen(temp), total = 0;<br /> for(i = 0; i < len; i++)<br /> total = total * 10 + int(temp[i] - '0');<br /> return total;<br /> }<br /> int main()<br /> {<br /> int i, j;<br /> scanf("%d", &n);<br /> init();<br /> for(i = 2; i <= n; i++)<br /> {<br /> for(j = 1; j < i; j++)<br /> {<br /> scanf("%s", temp);<br /> if(temp[0] == 'x') continue;<br /> int weight = getNum();<br /> insert(i, j, weight);<br /> insert(j, i, weight);<br /> }<br /> }<br /> dijkstra();<br /> int maxVal = -1;<br /> for(i = 1; i <= n; i++)<br /> if(dist[i] > maxVal)<br /> maxVal = dist[i];<br /> printf("%d/n", maxVal);<br /> return 0;<br /> }