求解跟图相关的问题时，经常用到矩阵。如果矩阵边比节点(n^2)少很多，可以考虑稀疏矩阵。
可以类似3元组表示法。开一个n个元素的指针数组，每个指针指向一边连续内存，这段连续内存里放的是[列号 边权]二元组，头部有DWORD值标识该列一共几个二元组。每一行按列号排好序，这样随机访问一个时，用二分查找，是O(log((k)(1/2)))的时间复杂度。
进一步优化：可以让每一列是一个hash_map，O(1)的时间复杂度了。但适用情况是k/n稍大一些，几千几万时，好一些。
求解跟图相关的问题时，经常用到矩阵。如果矩阵边比节点(n^2)少很多，可以考虑稀疏矩阵。
可以类似3元组表示法。开一个n个元素的指针数组，每个指针指向一边连续内存，这段连续内存里放的是[列号 边权]二元组，头部有DWORD值标识该列一共几个二元组。每一行按列号排好序，这样随机访问一个时，用二分查找，是O(log((k)(1/2)))的时间复杂度。
进一步优化：可以让每一列是一个hash_map，O(1)的时间复杂度了。但适用情况是k/n稍大一些，几千几万时，好一些。